POJ3691 DNA repair AC自动机+DP

　　首先庆祝1A。

　如果是单串的匹配，那么状态转移方程就是f[i][j]，表示匹配串的前 i 位最近9个数字的状态是 j 的最小改动，每个状态用状态压缩表示下就可以了。复杂度是指数级，对于较小的字符串还是可以接受的。但是这个有很多不必要的情况，因为很多转移都可以归纳到一起，即修改或者不修改，因此把方程改为表示匹配串的第 i 为模板串的第 j 个节点时的最优解，那么对于每个节点就只有4种转移状态了，即一个单串的DFA。同样，我们对于多个串建立一个AC自动机就可以了，转移方程：f[i][j]=Min{ f[i][j] , f[i][son] + c!=id }。

　　注意要考虑当前串的字串是不合法串的情况。

  1 //STATUS:C++_AC_79MS_4200KB
  2 #include<stdio.h>
  3 #include<stdlib.h>
  4 #include<string.h>
  5 #include<math.h>
  6 #include<iostream>
  7 #include<string>
  8 #include<algorithm>
  9 #include<vector>
 10 #include<queue>
 11 #include<stack>
 12 #include<map>
 13 #include<set>
 14 using namespace std;
 15 //define
 16 #define pii pair<int,int>
 17 #define mem(a,b) memset(a,b,sizeof(a))
 18 #define lson l,mid,rt<<1
 19 #define rson mid+1,r,rt<<1|1
 20 #define PI acos(-1.0)
 21 //typedef
 22 typedef __int64 LL;
 23 typedef unsigned __int64 ULL;
 24 //const
 25 const int N=1010;
 26 const int INF=0x3f3f3f3f;
 27 const int MOD=100000,STA=8000010;
 28 const LL LNF=1LL<<60;
 29 const double EPS=1e-8;
 30 const double OO=1e15;
 31 //Daily Use ...
 32 template<class T> T gcd(T a,T b){return b?gcd(b,a%b):a;}
 33 template<class T> T lcm(T a,T b){return a/gcd(a,b)*b;}
 34 template<class T> inline T Min(T a,T b){return a<b?a:b;}
 35 template<class T> inline T Max(T a,T b){return a>b?a:b;}
 36 template<class T> inline T Min(T a,T b,T c){return min(min(a, b),c);}
 37 template<class T> inline T Max(T a,T b,T c){return max(max(a, b),c);}
 38 template<class T> inline T Min(T a,T b,T c,T d){return min(min(a, b),min(c,d));}
 39 template<class T> inline T Max(T a,T b,T c,T d){return max(max(a, b),max(c,d));}
 40 //End
 41 
 42 char s[N];
 43 int idx[100];
 44 int ch[N][4];
 45 int val[N],f[N],dp[N][N],sta[N],ma[N];
 46 int sz,n,cnt;
 47 
 48 void init(){sz=1;mem(ch[0],0);}
 49 
 50 void insert(char *s,int v){
 51     int i,len=strlen(s),id,u=0;
 52     for(i=0;i<len;i++){
 53         id=idx[s[i]];
 54         if(!ch[u][id]){
 55             mem(ch[sz],0);
 56             val[sz]=0;
 57             ch[u][id]=sz++;
 58         }
 59         u=ch[u][id];
 60     }
 61     val[u]=v;
 62 }
 63 
 64 void getFail()
 65 {
 66     int c,u,r;
 67     queue<int> q;
 68     f[0]=0;
 69     ma[0]=0;sta[0]=cnt++;
 70     for(c=0;c<4;c++){
 71         u=ch[0][c];
 72         if(u){
 73             if(!val[u])ma[u]=cnt;sta[cnt++]=u;
 74             f[u]=0;
 75             q.push(u);
 76         }
 77     }
 78     while(!q.empty()){
 79         r=q.front();q.pop();
 80         for(c=0;c<4;c++){
 81             u=ch[r][c];
 82             if(!u){
 83                 ch[r][c]=ch[f[r]][c];
 84                 continue;
 85             }
 86             q.push(u);
 87             f[u]=ch[f[r]][c];
 88             if(val[r] || val[f[u]])val[u]=1;
 89             if(!val[u]){ma[u]=cnt;sta[cnt++]=u;}
 90         }
 91     }
 92 }
 93 
 94 int main()
 95 {
 96  //   freopen("in.txt","r",stdin);
 97     int i,j,t,c,test=1,ans,len,ok,id,u;
 98     char temp[23];
 99     idx['A']=0;idx['C']=1;idx['T']=2,idx['G']=3;
100     while(~scanf("%d",&n) && n)
101     {
102         init();
103         for(i=0;i<n;i++){
104             scanf("%s",temp);
105             insert(temp,1);
106         }
107         scanf("%s",s);
108         len=strlen(s);
109 
110         cnt=0;
111         mem(dp,INF);
112         dp[0][0]=0;
113         getFail();
114         for(i=0;i<len;i++){
115             ok=0;
116             id=idx[s[i]];
117             for(j=0;j<cnt;j++){
118                 if(dp[i][j]==INF)continue;
119                 for(c=0;c<4;c++){
120                     u=ch[sta[j]][c];
121                     t=(c!=id);
122                     if(!val[u]){
123                         ok=1;
124                         dp[i+1][ma[u]]=Min(dp[i+1][ma[u]],dp[i][j]+t);
125                     }
126                 }
127             }
128             if(!ok)break;
129         }
130 
131         if(ok){
132             ans=INF;
133             for(i=0;i<cnt;i++){
134                 ans=Min(ans,dp[len][i]);
135             }
136         }
137         else ans=-1;
138 
139         printf("Case %d: %d\n",test++,ans);
140     }
141     return 0;
142 }