修复dna

#include<bits/stdc++.h>

using namespace std;

const int N=55,S=22,M=1002,INF=0x3f3f3f3f;

int n,m;
int tr[N*S][5],dar[N*S],idx;
char str[M];
int q[N*S],ne[N*S];
int f[M][N*S];
map<char,int> ch;

void insert()
{
	int p=0;
	for(int i=0;str[i];i++)
	{
		int t=ch[str[i]];
		if(!tr[p][t]) tr[p][t]=++idx;
		p=tr[p][t];
	}
	dar[p]=1;
}

void build()
{
	int hh=0,tt=-1;
	for(int i=0;i<4;i++)
		if(tr[0][i])
			q[++tt]=tr[0][i];
	
	while(hh<=tt)
	{
		int t=q[hh++];
		for(int i=0;i<4;i++)
		{
			int c=tr[t][i];
			if(!c) tr[t][i]=tr[ne[t]][i];
			else
			{
				ne[c]=tr[ne[t]][i];
				q[++tt]=c;
				dar[c]|=dar[ne[c]];
			}
		}
	}
}

int main()
{
	ch['A']=0,ch['G']=1,ch['C']=2,ch['T']=3;
	int T=1;
	
	while(scanf("%d",&n),n)
	{
		idx=0;
		memset(tr,0,sizeof tr);
		memset(q,0,sizeof q);
		memset(ne,0,sizeof ne);
		memset(dar,0,sizeof dar);
		memset(f,INF,sizeof f);
		 
		for(int i=1;i<=n;i++)
		{
			scanf("%s",str);
			insert();
		}
		
		build();
		
		scanf("%s",str+1);
		m=strlen(str+1);
		
		f[0][0]=0;
		for(int i=0;i<m;i++)
			for(int j=0;j<=idx;j++)
				for(int k=0;k<4;k++)
				{
					int u=tr[j][k];	
					if(!dar[u]) f[i+1][u]=min(f[i+1][u],f[i][j]+(ch[str[i+1]]!=k));		
				}
		
		int res=INF;
		for(int i=0;i<=idx;i++) res=min(res,f[m][i]);
		
		if(res==INF) res=-1;
		printf("Case %d: %d\n",T++,res); 
	}
	
	return 0;
}