有$n$个DNA串，以及一个DNA主串。你需要最小化更改次数，使得更改后的DNA串不包含匹配串中的任何一个。
因为已经写过那道SRM的KMP+dp，这道题写起来反而比POJ2778轻松不少。
定义dp[i][j]表示第$i$个点，在自动机上的点是$j$
利用AC自动机的边瞎比转移即可。
再次为TC上那个AC自动机模板点赞啊，太TM方便了。。
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int M=1e3+5;
int n,id[100];
char str[M];
inline void Init(){
id['A']=0,id['T']=1,id['C']=2,id['G']=3;
}
struct node{
int to[4],d,g;
}tr[M];
int allc=1,que[M];
inline void Insert(){
int len=strlen(str),rt=1;
for(int i=0;i<len;++i){
int c=id[str[i]];
if(!tr[rt].to[c])tr[rt].to[c]=++allc;
rt=tr[rt].to[c];
}
tr[rt].d=1;
}
inline void build(){
int l=0,r=0;
for(que[r++]=1;l<r;){
int u=que[l++];
for(int i=0,j,s;i<4;++i){
for(j=tr[u].g;j;j=tr[j].g)
if(tr[j].to[i])break;
if(s=tr[u].to[i]){
tr[s].g=j?tr[j].to[i]:1;
tr[s].d|=tr[tr[s].g].d;
que[r++]=s;
}
else tr[u].to[i]=j?tr[j].to[i]:1;
}
}
}
inline void Min(int &a,int b){
if(a==-1||a>b)a=b;
}
int dp[2][M],_;
inline void clear(){
for(int i=1;i<=allc;++i)
for(int j=tr[i].d=tr[i].g=0;j<4;++j)
tr[i].to[j]=0;
allc=1;
}
inline void gao(){
clear();
for(int i=1;i<=n;++i){
scanf("%s",str);
Insert();
}
build();
scanf("%s",str);
int len=strlen(str),cur=0,nxt=1;
memset(dp,-1,sizeof(dp));
dp[nxt][1]=0;
//dp[i][j]:node i match j the minmum change
for(int i=0;i<len;++i){
cur^=1,nxt^=1;
memset(dp[nxt],-1,sizeof(dp[nxt]));
for(int j=1;j<=allc;++j){
if(dp[cur][j]==-1)continue;
for(int k=0;k<4;++k)
if(!tr[tr[j].to[k]].d)
Min(dp[nxt][tr[j].to[k]],dp[cur][j]+(k!=id[str[i]]));
}
}
int res=-1;
for(int i=1;i<=allc;++i)
if(~dp[nxt][i])Min(res,dp[nxt][i]);
printf("Case %d: %d\n",++_,res);
}
int main(){
Init();
for(;cin>>n,n;)gao();
return 0;
}