poj 3691

AC自动机的失配函数的利用和DP，Trie图中的每个节点代表一种状态，即一个字符串的后缀为从根节点到本节点的字符串。就是说把字符串根据他的后缀分为不同的类别，AC自动机上的每一个节点代表一个类别。在一个字符串的后面再加一个字符，此字符串就会从Tire图中的一个节点转移到另一个节点，这个过程可通过失配函数的求解过程中求出。其中有的节点所代表的类是不合法的，要记录下来。然后就是dp,ans[i][j]表示母串的i长度的串要变成状态为j的串所需最小修改次数。初始化为无穷大，如果j不合法不求，并且j的下一个转移得到的节点也不从j转移得到，最后比较每个节点的ans[len][j],得到最小值。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <queue>
  5 using namespace std;
  6 const int maxn=50+10;
  7 const int inf=0x3f3f3f3f;
  8 int n;
  9 int ch[maxn*20][4];
 10 int val[maxn*20],tot,f[maxn*20];
 11 int ans[1000+10][maxn*20];
 12 int getV(char c)
 13 {
 14     switch(c)
 15     {
 16     case 'A':return 0;
 17     case 'G':return 1;
 18     case 'C':return 2;
 19     case 'T':return 3;
 20     }
 21 }
 22 void Insert(char *s)
 23 {
 24     int u=0,len=strlen(s),i,tv;
 25     for(i=0;i<len;i++)
 26     {
 27         tv=getV(s[i]);
 28         if(!ch[u][tv]) ch[u][tv]=tot++;
 29         u=ch[u][tv];
 30     }
 31     val[u]=1;
 32 }
 33 void getFail()
 34 {
 35     queue<int> q;
 36     f[0]=0;
 37     int i,u;
 38     for(i=0;i<4;i++)
 39     {
 40         u=ch[0][i];
 41         if(u)
 42         {
 43             f[u]=0;
 44             q.push(u);
 45             //printf("%d %d\n",u,val[u]);
 46         }
 47     }
 48     int v,r;
 49     while(!q.empty())
 50     {
 51         r=q.front();q.pop();
 52         for(i=0;i<4;i++)
 53         {
 54             u=ch[r][i];
 55             if(!u) { ch[r][i]=ch[f[r]][i]; }
 56             else
 57             {
 58             if(val[r]) val[u]=1;//这部很关键
 59             q.push(u);
 60             v=f[r];
 61             while(v&&!ch[v][i]) v=f[v];
 62             f[u]=ch[v][i];
 63             if(val[f[u]]) val[u]=1;//这步很关键
 64             }
 65          //   printf("%d %d\n",u,val[u]);
 66         }
 67     }
 68 }
 69 int main()
 70 {
 71     int cas=0;
 72     while(scanf("%d",&n)&&n)
 73     {
 74         int i,j;
 75         char s[1000+10];
 76         tot=1;
 77         memset(ch,0,sizeof(ch));
 78         memset(val,0,sizeof(val));
 79         for(i=0;i<n;i++)
 80         {
 81             scanf("%s",s);
 82             Insert(s);
 83         }
 84         scanf("%s",s);
 85         getFail();
 86         int len=strlen(s);
 87         for(i=0;i<=len;i++)
 88         {
 89             for(j=0;j<tot;j++)
 90                 ans[i][j]=inf;
 91         }
 92         ans[0][0]=0;
 93         int k,v;
 94         for(i=0;i<len;i++)
 95         {
 96             for(j=0;j<tot;j++)
 97             {
 98                 if(ans[i][j]<inf)
 99                 {
100                 for(k=0;k<4;k++)
101                 {
102                     if(!val[ch[j][k]])
103                     {
104                         v=ch[j][k];
105                         ans[i+1][v]=min(ans[i+1][v],ans[i][j]+(getV(s[i])==k?0:1));
106                     }
107                 }
108             }
109             }
110         }
111         int re=inf;
112         for(i=0;i<tot;i++) re=min(re,ans[len][i]);
113         printf("Case %d: %d\n",++cas,re<inf?re:-1);
114     }
115     return 0;
116 }