题目大意：
改动文本串的上的字符，使之不出现上面出现的串。问最少改动多少个。
思路分析：
dp[i][j]表示如今 i 个字符改变成了字典树上的 j 节点。
然后顺着自己主动机一直转移方程。
注意合法与不合法。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define inf 0x3f3f3f3f
using namespace std; const char tab = 0;
const int max_next = 4;
int idx;
struct trie
{
struct trie *fail;
struct trie *next[max_next];
int isword;
int index;
trie()
{
isword=0;
memset(next,NULL,sizeof next);
fail=NULL;
}
};
int rev[256];
trie *que[100005],ac[100005];
int head,tail; trie *New()
{
trie *temp=&ac[idx];
for(int i=0;i<4;i++)temp->next[i]=NULL;
temp->fail=NULL;
temp->isword=0;
temp->index=idx++;
return temp;
}
void Insert(trie *root,char *word,int len){
trie *t=root;
for(int i=0;i<len;i++){
if(t->next[rev[word[i]]]==NULL)
t->next[rev[word[i]]]=New();
t=t->next[rev[word[i]]];
}
t->isword++;
} void acbuild(trie *root){
int head=0,tail=0;
que[tail++]=root;
root->fail=NULL;
while(head<tail){
trie *temp=que[head++],*p;
for(int i=0;i<max_next;i++){
if(temp->next[i]){
if(temp==root)temp->next[i]->fail=root;
else {
p=temp->fail;
while(p!=NULL){
if(p->next[i]){
temp->next[i]->fail=p->next[i];
break;
}
p=p->fail;
}
if(p==NULL)temp->next[i]->fail=root;
}
if(temp->next[i]->fail->isword)temp->next[i]->isword++;
que[tail++]=temp->next[i];
}
else if(temp==root)temp->next[i]=root;
else temp->next[i]=temp->fail->next[i];
}
}
} void del(trie *root)
{
for(int i=0;i<max_next;i++)
if(root->next[i])del(root->next[i]);
free(root);
} int dp[2005][2005];
int solve(char *word,int len)
{
memset(dp,0x3f,sizeof dp);
dp[0][0]=0;
for(int i=1;i<=len;i++)
{
for(int j=0;j<idx;j++)
{
if(ac[j].isword)continue;
if(dp[i-1][j]==inf)continue;
for(int k=0;k<4;k++)
{
int p=ac[j].next[k]->index;
if(ac[p].isword)continue;
dp[i][p]=min(dp[i][p],dp[i-1][j]+(k!=rev[word[i-1]]));
}
}
}
int ans=inf;
for(int i=0;i<idx;i++)
ans=min(ans,dp[len][i]);
return ans==inf? -1:ans;
}
char word[10005];
int main()
{
rev['A']=0;
rev['G']=1;
rev['C']=2;
rev['T']=3; int n,cas=1;
while(scanf("%d",&n)!=EOF && n)
{
idx=0;
trie *root=New();
for(int i=1;i<=n;i++)
{
scanf("%s",word);
Insert(root,word,strlen(word));
}
acbuild(root);
scanf("%s",word);
printf("Case %d: %d\n",cas++,solve(word,strlen(word)));
}
return 0;
}