[hdu2457]DNA repair(AC自动机+dp)

题意：给出一些不合法的模式DNA串，给出一个原串，问最少需要修改多少个字符，使得原串中不包含非法串。

解题关键：多模式串匹配->AC自动机，求最优值->dp，注意在AC自动机上dp的套路。

AC自动机上的每个节点其实就是一种状态，进行模式匹配其实就是进行边的匹配

令$dp[i][j]$表示字符串长度为$i$时到达AC自动机上某个状态所需要修改的最小值。

转移方程：$dp[i + 1][Next[j][k]] = min (dp[i][j] + (k! = str[i]),dp[i + 1][Next[j][k]])$

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<cstdlib>
  5 #include<cstring>
  6 #include<iostream>
  7 #include<queue>
  8 #define inf 0x3f3f3f3f
  9 using namespace std;
 10 typedef long long ll;
 11 const int N=4;
 12 const int MAXN=1010;
 13 ll m,n;
 14 int dp[1002][MAXN];
 15 struct Trie{
 16     int Next[MAXN][N],Fail[MAXN],root,tot;
 17     bool End[MAXN];
 18     int newnode(){
 19         for(int i=0;i<N;i++) Next[tot][i]=-1;
 20         End[tot++]=false;
 21         return tot-1;
 22     }
 23     void init(){
 24         tot=0;
 25         root=newnode();
 26     }
 27     void insert(char buf[]){
 28         int len=strlen(buf),now=root,k;
 29         for(int i=0;i<len;i++){
 30             if(buf[i]=='A') k=0;
 31             else if(buf[i]=='G') k=1;
 32             else if(buf[i]=='C') k=2;
 33             else k=3;
 34             if(Next[now][k]==-1)  Next[now][k]=newnode();
 35             now=Next[now][k];
 36         }
 37         End[now]=true;
 38     }
 39     void build(){
 40         queue<int>que;
 41         Fail[root]=root;
 42         for(int i=0;i<N;i++){ 
 43             if(Next[root][i]==-1) Next[root][i]=root;
 44             else{
 45                 Fail[Next[root][i]]=root;
 46                 que.push(Next[root][i]);
 47             }
 48         } 
 49         while(!que.empty()){
 50             int now=que.front();
 51             que.pop();
 52             if(End[Fail[now]]) End[now]=true;
 53             for(int i=0;i<N;i++){
 54                 if(Next[now][i]==-1) Next[now][i]=Next[Fail[now]][i];//Next指针都已经建立好 
 55                 else{
 56                     Fail[Next[now][i]]=Next[Fail[now]][i];
 57                     que.push(Next[now][i]);
 58                 }
 59             }
 60         }
 61     }
 62     int solve(char buf[]){
 63         int len=strlen(buf);
 64         for(int i=0;i<=len;i++)    for(int j=0;j<=tot;j++) dp[i][j]=inf;
 65         dp[0][0]=0;
 66         for(int i=0;i<len;i++){//最主要的事情就是分清边和点 
 67             int tmp;
 68             if(buf[i]=='A') tmp=0;
 69             else if(buf[i]=='G') tmp=1;
 70             else if(buf[i]=='C') tmp=2;
 71             else tmp=3;
 72             for(int j=0;j<tot;j++){
 73                 if(dp[i][j]==inf||End[j]) continue;
 74                 for(int k=0;k<4;k++){
 75                     int u=Next[j][k];
 76                     if(End[u]) continue;
 77                     dp[i+1][u]=min(dp[i][j]+(tmp!=k),dp[i+1][u]);
 78                 }
 79             }
 80         }
 81         int ans=inf;
 82         for(int i=0;i<tot;i++) ans=min(ans,dp[len][i]);
 83         return ans==inf?-1:ans;
 84     }
 85 };
 86 
 87 Trie ac;
 88 char buf[2200];
 89 int main(){
 90     int ca=0;
 91     while(scanf("%d",&n)&&n){
 92         ca++;
 93         ac.init();
 94         for(int i=0;i<n;i++) scanf("%s",buf),ac.insert(buf);
 95         ac.build();
 96         scanf("%s",buf);
 97         int ans=ac.solve(buf);
 98         printf("Case %d: %d
",ca,ans);
 99     }
100 }