＃i nclude <iostream>
＃i nclude <cstdio>
＃i nclude <cstring>
＃i nclude <queue>
#define maxn 1010
using namespace std;
int next[maxn][4],f[maxn][maxn],N,n,cod[500],fail[maxn],L;
bool tag[maxn];
char s[maxn];
void insert()
{
int cur=0,tep;
for (int i=0; s[i]; i++)
{
tep=cod[int(s[i])];
if (next[cur][tep]==0)
next[cur][tep]=++N;
cur=next[cur][tep];
}
tag[cur]=true;
}
void buildAC()
{
queue<int> Q;
int cur,child,k;
Q.push(0);
while (!Q.empty())
{
cur=Q.front();
Q.pop();
for (int i=0; i<4; i++)
{
child=next[cur][i];
if (child)
{
Q.push(child);
if (cur==0) fail[child]=0;
else
{
k=fail[cur];
while (k && next[k][i]==0) k=fail[k];
if (next[k][i]) fail[child]=next[k][i];
else fail[child]=0;
}
if (tag[fail[child]]) tag[child]=true;
}
else
{
k=fail[cur];
next[cur][i]=next[k][i];
}
}
}
}
int main()
{
int tep,ans,cas=0;
cod['A']=0; cod['T']=1;
cod['G']=2; cod['C']=3;
while (scanf("%d",&n) && n)
{
memset(next,0,sizeof next);
memset(tag,false,sizeof tag);
memset(f,1,sizeof f);
memset(fail,0,sizeof fail);
N=0; ans=~0U>>1;
while (n--)
{
scanf("%s",s);
insert();
}
buildAC();
scanf("%s",s);
L=strlen(s);
f[0][0]=0;
for (int i=0; s[i]; i++)
{
tep=cod[int(s[i])];
for (int j=0; j<=N; j++)
{
if (tag[j]) continue;
if (f[i][j]==f[1009][1009]) continue;
for (int k=0; k<4; k++)
{
if (tag[next[j][k]]) continue;
if (tep==k)
f[i+1][next[j][k]]=min(f[i+1][next[j][k]],f[i][j]);
else f[i+1][next[j][k]]=min(f[i+1][next[j][k]],f[i][j]+1);
}
}
}
for (int i=0; i<=N; i++)
if (f[L][i]<ans) ans=f[L][i];
printf("Case %d: ",++cas);
if (ans<f[1009][1009]) printf("%d\n",ans);
else printf("-1\n");
}
return 0;
}
^_^
