POJ 3691 DNA repair 基于AC自己主动机DP-白红宇

POJ 3691 DNA repair 基于AC自己主动机DP

阅读量：6005 次

发布时间：2019-06-20

本文共 2864 字，大约阅读时间需要 9 分钟。

dp[i][j] 它表示的长度 i 下游前缀 j 更改节点的最小数量。

很清楚dp[0][0] = 0;

dp[ i ][ j ] = min(dp[ i ][ j ],dp[i-1][k] + (j == k ?

0 : 1)),当且仅当j。k满足下列条件时。

j 不为某条模式串的末节点且 j 到 root 的由失败指针组成的路径上无末节点。

j 是k的儿子节点或者 j 的父节点可由 k 沿着失败指针找到。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #pragma comment(linker, "/STACK:1024000000");#define EPS (1e-8)#define LL long long#define ULL unsigned long long#define _LL __int64#define INF 0x3f3f3f3fusing namespace std;const int MAXN = 4;struct N{ int next[MAXN],flag,fail;} st[1010];int Top;int sel(char c){ if(c == 'A') return 0; if(c == 'G') return 1; if(c == 'C') return 2; return 3;}int creat(){ memset(st[Top].next,-1,sizeof(st[Top].next)); st[Top].fail = -1,st[Top].flag = 0; return Top++;}int dp[1010][1010];char s[1010];void Get_Trie(int root,char *s){ int site = 1; while(s[site] != '\0') { if(st[root].next[sel(s[site])] == -1) st[root].next[sel(s[site])] = creat(); root = st[root].next[sel(s[site])]; ++site; } st[root].flag = 1;}int Get_Fail(int site,int tar){ while(site != -1 && st[site].next[tar] == -1) site = st[site].fail; if(site == -1) return 0; return st[site].next[tar];}queue
              
                q;void Get_Fail(int root){ q.push(root); st[root].fail = -1; int f; while(q.empty() == false) { f = q.front(); q.pop(); for(int i = 0; i < MAXN; ++i) { if(st[f].next[i] != -1) { st[st[f].next[i]].fail = Get_Fail(st[f].fail,i); q.push(st[f].next[i]); } } }}bool Is_Safe(int site){ if(site == -1) return true; if(st[site].flag || Is_Safe(st[site].fail) == false) return false; return true;}int Is_Safe(int site,int tar){ if(site == -1) return 0; if(st[site].next[tar] != -1) { if(st[st[site].next[tar]].flag != 0 || Is_Safe(st[site].next[tar]) == false) return -1; return st[site].next[tar]; } return Is_Safe(st[site].fail,tar);}void Match(int root,char *s){ memset(dp,INF,sizeof(dp)); dp[0][0] = 0; int site,i,j,tmp; for(site = 1; s[site] != '\0'; ++site) { for(i = 0; i < Top; ++i) { if(dp[site-1][i] == INF) continue; for(j = 0; j < 4; ++j) { if(st[i].next[j] != -1 && st[st[i].next[j]].flag != 0) continue; if(st[i].next[j] != -1 && Is_Safe(st[i].next[j])) { dp[site][st[i].next[j]] = min(dp[site][st[i].next[j]],dp[site-1][i] + (j == sel(s[site]) ? 0 : 1)); continue; } tmp = Is_Safe(i,j); if(tmp == -1) continue; dp[site][tmp] = min(dp[site][tmp],dp[site-1][i] + (j == sel(s[site]) ? 0 : 1)); } } }}int main(){ int i,n; int icase = 1; int root; while(scanf("%d",&n) && n) { Top = 0; root = creat(); for(int i = 1; i <= n; ++i) { scanf("%s",s+1); Get_Trie(root,s); } Get_Fail(root); scanf("%s",s+1); Match(root,s); int anw = INF,len = strlen(s+1); for(i = 0; i < Top; ++i) anw = min(anw,dp[len][i]); printf("Case %d: %d\n",icase++,anw == INF ? -1 : anw); } return 0;}