题目链接：

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

思路：沿着AC自动机dp，dp[i][j]表示前i个字符，当前为状态j的时候，需要修改的最少字符数。

代码：

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
               10 using namespace std; 11 typedef long long LL; 12 const LL MAXN=2e3+10; 13 const LL INF=0x3f3f3f3f; 14 15 struct AC 16 { 17 int ch[MAXN][4]; 18 int val[MAXN]; 19 int chr[MAXN]; 20 int sz; 21 AC() { init(); } 22 void init() { sz=1; memset(ch[0],0,sizeof(ch[0])); memset(val,0,sizeof(val));} 23 int idx(char c) 24 { 25 if(c=='A') return 0; 26 if(c=='G') return 1; 27 if(c=='C') return 2; 28 if(c=='T') return 3; 29 return 4; 30 } 31 void insert(char *s) 32 { 33 int u=0,n=strlen(s); 34 for(int i=0;i
              

q; 77 f[0]=0; 78 for(int c=0;c<4;c++) 79 { 80 int u=ch[0][c]; 81 if(u) {f[u]=0;q.push(u);last[u]=0;} 82 } 83 while(!q.empty()) 84 { 85 int r=q.front();q.pop(); 86 for(int c=0;c<4;c++) 87 { 88 int u=ch[r][c]; 89 if(!u) 90 { 91 ch[r][c]=ch[f[r]][c]; 92 continue; 93 } 94 q.push(u); 95 int v=f[r]; 96 while(v && !ch[v][c]) v=f[v]; 97 f[u]=ch[v][c]; 98 last[u]=val[f[u]]?f[u]:last[f[u]]; 99 if(!val[u]) val[u]=val[last[u]];100 }101 }102 }103 };104 AC T;105 int f[MAXN][MAXN];106 char s[MAXN];107 int main()108 {109 #ifdef LOCAL110 freopen("in.txt","r",stdin);111 // freopen("out.txt","w",stdout);112 #endif113 int n;114 int tt=0;115 while(scanf("%d",&n)!=EOF && n)116 {117 tt++;118 T.init();119 for(int i=1;i<=n;i++)120 {121 scanf("%s",s);122 T.insert(s);123 }124 T.getFail();125 scanf("%s",s);126 int l=strlen(s);127 memset(f,INF,sizeof(f));128 for(int k=0;k<4;k++) if(!T.val[T.ch[0][k]])129 f[0][T.ch[0][k]]=(k==T.idx(s[0]))?0:1;130 for(int i=0;i

=INF) ans=-1;141 printf("Case %d: %d\n",tt,ans);142 }143 return 0;144 }