题目大意：给你$n$个串$p_i$，最后再给一个串$s$（字符集均为A,C,G,T四个字符中的一个）。问你串$s$最少要更改多少个字符（更改后的字符也只能是ACGT），才能满足s中不包含$p_i$$（1≤i≤n）$
数据范围：$n≤50$，$|p|≤20$，$|s|≤100$。不超过100组数据。
此题显然是一个AC自动机DP题。
我们首先建出字符串集合$p$的AC自动机。
不难发现，这个自动机中有很多个节点是不能被遍历到的（如果遍历到了串就会包含某些不合法串）
设$f[i][j]$表示我们已经扫描完了串$s$中前i个字符，且当前遍历到了自动机第$j$号点时，最少需要改变的字符数量。
然后枚举我们要在第$i+1$位填什么字符，是否会增加贡献。
也就是说，我们可以用$f[i][j]$的值来更新$f[i+1][ch[j][char]]$，其中$ch[j][char]$表示在$j$号节点往下填字符$char$会跑到哪个点（详见代码）
然后就没有了
复杂度:$O(nps)$。
1 #include<bits/stdc++.h> 2 #define M 1005 3 #define INF 16843009 4 #define fmin(x,y) ((x)>(y)?(x)=(y):0) 5 using namespace std; 6 7 int id[128]={0}; 8 9 struct trie{int a[4],fail,no;}a[M];int use=0; 10 void add(char c[]){ 11 int len=strlen(c),now=0; 12 for(int i=0;i<len;i++){ 13 int k=id[c[i]]; 14 if(a[now].a[k]) now=a[now].a[k]; 15 else a[now].a[k]=++use,now=use; 16 } 17 a[now].no=1; 18 } 19 void makefail(){ 20 queue<int> q; q.push(0); 21 while(!q.empty()){ 22 int u=q.front(); q.pop(); 23 for(int i=0;i<4;i++) if(a[u].a[i]){ 24 a[a[u].a[i]].no|=a[u].no; 25 q.push(a[u].a[i]); 26 if(u){ 27 int f=a[u].fail; 28 while(f&&a[f].a[i]==0) f=a[f].fail; 29 a[a[u].a[i]].fail=a[f].a[i]; 30 a[a[u].a[i]].no|=a[a[f].a[i]].no; 31 } 32 }else{ 33 a[u].a[i]=a[a[u].fail].a[i]; 34 } 35 } 36 } 37 38 int s[M]={0},f[M][M]={0};char str[M]={0}; 39 40 int main(){ 41 id['A']=0; id['C']=1; id['G']=2; id['T']=3; 42 for(int cas=1;;cas++){ 43 memset(s,0,sizeof(s)); memset(a,0,sizeof(a)); use=0; 44 int n; scanf("%d",&n); 45 if(n==0) return 0; 46 for(int i=1;i<=n;i++){ 47 scanf("%s",str); 48 add(str); 49 } 50 makefail(); 51 scanf("%s",str+1); int len=strlen(str+1); 52 for(int i=1;i<=len;i++) s[i]=id[str[i]]; 53 memset(f,1,sizeof(f)); f[0][0]=0; 54 for(int i=0;i<len;i++){ 55 for(int j=0;j<=use;j++) 56 if(f[i][j]!=INF){ 57 for(int k=0;k<4;k++){ 58 int pls=(k!=s[i+1]); 59 if(a[a[j].a[k]].no) continue; 60 fmin(f[i+1][a[j].a[k]],f[i][j]+pls); 61 } 62 } 63 } 64 int minn=INF; 65 for(int j=0;j<=use;j++) if(a[j].no==0) 66 fmin(minn,f[len][j]); 67 printf("Case %d: ",cas); 68 if(minn==INF) cout<<-1<<endl; 69 else cout<<minn<<endl; 70 } 71 }