题意:给N个串，一个大串，要求在最小的改变代价下，得到一个不含上述n个串的大串。
思路:dp，f[i][j]代表大串中第i位，AC自动机上第j位的最小代价。
1 #include<algorithm> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<iostream> 6 #include<queue> 7 std::queue<int>Q; 8 int ch[10005][5],end[10005],f[1005][1005],sz,root,fail[100005],n,Tcase; 9 char s[10005]; 10 int newnode(){ 11 for (int i=0;i<=3;i++) 12 ch[sz][i]=-1; 13 end[sz]=0; 14 sz++; 15 return sz-1; 16 } 17 void clear(){ 18 sz=0;root=newnode(); 19 } 20 int num(char c){ 21 if (c=='A') return 0; 22 else 23 if (c=='T') return 1; 24 else 25 if (c=='G') return 2; 26 else 27 if (c=='C') return 3; 28 return 0; 29 } 30 void insert(){ 31 scanf("%s",s); 32 int len=strlen(s); 33 int now=root; 34 for (int i=0;i<len;i++){ 35 if (ch[now][num(s[i])]==-1) ch[now][num(s[i])]=newnode(); 36 now=ch[now][num(s[i])]; 37 } 38 end[now]=1; 39 } 40 void build(){ 41 int now=root; 42 std::queue<int>Q; 43 fail[root]=root; 44 for (int i=0;i<=3;i++) 45 if (ch[root][i]==-1) ch[root][i]=root; 46 else fail[ch[root][i]]=root,Q.push(ch[root][i]); 47 while (!Q.empty()){ 48 int now=Q.front();Q.pop(); 49 if (end[fail[now]]==1) end[now]|=1; 50 for (int i=0;i<=3;i++){ 51 if (ch[now][i]==-1) ch[now][i]=ch[fail[now]][i]; 52 else fail[ch[now][i]]=ch[fail[now]][i],Q.push(ch[now][i]); 53 } 54 } 55 } 56 void dp(){ 57 scanf("%s",s); 58 int len=strlen(s); 59 for (int i=0;i<=len;i++) 60 for (int j=0;j<=sz;j++) 61 f[i][j]=99999999; 62 f[0][root]=0; 63 for (int i=0;i<len;i++) 64 for (int j=0;j<sz;j++) 65 if (f[i][j]<99999999){ 66 for (int k=0;k<=3;k++){ 67 int now=ch[j][k]; 68 if (end[now]) continue; 69 int tmp; 70 if (k==num(s[i])) tmp=f[i][j]; 71 else tmp=f[i][j]+1; 72 f[i+1][now]=std::min(f[i+1][now],tmp); 73 } 74 } 75 int ans=99999999; 76 for (int i=0;i<sz;i++) 77 ans=std::min(ans,f[len][i]); 78 if (ans==99999999) ans=-1; 79 printf("%d\n",ans); 80 } 81 int main(){ 82 while (scanf("%d",&n)!=EOF){ 83 if (n==0) return 0; 84 Tcase++; 85 printf("Case %d: ",Tcase); 86 clear(); 87 for (int i=1;i<=n;i++) 88 insert(); 89 build(); 90 dp(); 91 } 92 }