AC自动机+DP
对于AC自动机的bfs，这里加了一点改进。
-
引入了一个叫危险结点的东西，所谓危险结点，就是在字典树中以这个点结尾的字符串，是包含模式串的。
-
如果某个点
p没有了子节点，辣么我们需要将点p的子节点指向p的失败指针的子节点，这样是为了当穷途末路到达模式串的末尾时，就可以到一个可以查找的地方 -
值得注意的就是，如果一个点x，他的儿子son，x的失败指针为j，由失败指针的定义可知，s[j]为s[x]的后缀，所以如果j也有一个和son字符一样的儿子，那么，son的失败指针就是就是j的儿子啦！这样是满足失败指针的定义的。
-
如果某个点的失败指针是危险节点，那么这个点也要标记为危险结点
对于DP
-
f[i][j]表示原字符串第i位，字典树上的结点j，当i的后缀与j到跟组成的字符串完全匹配的最小修改值 -
注意如果这个点是危险结点，那么就不能更新
f[i][j]了，因为如果转移了，那就不符合题目要求了 -
这个转移方程很好想，就是
f[i+1][son]=f[i][j]+(a[i+1]!=k)，k就是son的字符，son是j的儿子，根据定义，就很好理解啦！ -
答案就是
f[n][i](i为树上所有的节点)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char s[60],change[1100];
int slen,tot,n;
struct char_tree{int son[5],end,fail;}tr[110000];
void clean(int x)
{
tr[x].end=0;tr[x].fail=-1;
memset(tr[x].son,-1,sizeof(tr[x].son));
}
int id(char c)
{
if(c=='A')return 1;
else if(c=='C')return 2;
else if(c=='G')return 3;
else return 4;
}
void build_tree(int root)
{
int x=root;
for(int i=1;i<=slen;i++)
{
int j=id(s[i]);
if(tr[x].son[j]==-1)tr[x].son[j]=++tot,clean(tot);
x=tr[x].son[j];
}
tr[x].end++;
}
int head,tail,list[2100000];
void bfs()
{
head=1;tail=1;memset(list,0,sizeof(list));
while(head<=tail)
{
int x=list[head];
for(int i=1;i<=4;i++)
{
int child=tr[x].son[i];
if(child==-1)
{
if(x==0)tr[x].son[i]=0;
else tr[x].son[i]=tr[tr[x].fail].son[i];
continue;
}
if(x==0)tr[child].fail=0;
else
{
int j=tr[x].fail;
while(j!=-1)
{
if(tr[j].son[i]!=-1)
{
tr[child].fail=tr[j].son[i];
int tmp=tr[j].son[i];if(tr[tmp].end!=0)tr[child].end=1;
break;
}
j=tr[j].fail;
}
if(j==-1)tr[child].fail=0;
}
list[++tail]=child;
}
head++;
}
}
int f[2100][2100];
int DP()
{
for(int i=0;i<=n;i++)for(int j=0;j<=tot;j++)f[i][j]=1e9;f[0][0]=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<=tot;j++)
{
if(f[i][j]==1e9)continue;
for(int k=1;k<=4;k++)
{
int child=tr[j].son[k];
if(tr[child].end!=0)continue;
f[i+1][child]=min(f[i+1][child],f[i][j]+(id(change[i+1])!=k));
}
}
}
int ans=1e9;
for(int i=0;i<=tot;i++)ans=min(ans,f[n][i]);
if(ans==1e9)ans=-1;
return ans;
}
int main()
{
int t=0;
while(scanf("%d",&n)!=EOF)
{
if(n==0)break;
t++;clean(0);
for(int i=1;i<=n;i++)
{
scanf("%s",s+1);slen=strlen(s+1);
build_tree(0);
}
bfs();
scanf("%s",change+1);n=strlen(change+1);
printf("Case %d: %d
",t,DP());
}
return 0;
}