从开始节点往下走，不能走到病毒节点，如果当前状态与原始串不一样就+1，取一个最小值.
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
#include<string>
using namespace std;
#define N 1005
#define LL long long
#define INF 0xfffffff
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
const int child_num = ;
char vir[];
char s[N];
class AC
{
private:
int ch[N][child_num];
int fail[N];
int Q[N];
int val[N];
int sz;
int id[];
char po[];
int dp[N][N];
public:
void init()
{
fail[] = ;
id['A'] = ,id['G'] = ,id['T'] = ,id['C'] = ;
po[] = 'A',po[] = 'G',po[] = 'T',po[] = 'C';
}
void reset()
{
memset(ch[],,sizeof(ch[]));
memset(val,,sizeof(val));
sz = ;
}
void insert(char *a,int key)
{
int p = ;
for(; *a ; a++)
{
int d= id[*a];
if(ch[p][d]==)
{
memset(ch[sz],,sizeof(ch[sz]));
s[sz] = *a;
ch[p][d] = sz++;
}
p = ch[p][d];
}
val[p] = (<<key);
}
void construct()
{
int i,head=,tail = ;
for(i = ; i < child_num ;i++)
{
if(ch[][i])
{
fail[ch[][i]] = ;
Q[tail++] = ch[][i];
}
}
while(head!=tail)
{
int u = Q[head++];
val[u]|=val[fail[u]];
for(i = ; i < child_num ; i++)
{
if(ch[u][i])
{
fail[ch[u][i]] = ch[fail[u]][i];
Q[tail++] = ch[u][i];
}
else ch[u][i] = ch[fail[u]][i];
}
}
}
void work(int n,int kk)
{
int i,j,g;
for(i = ; i <= n ;i++)
for(j = ;j <= sz ; j++)
dp[i][j] = INF;
dp[][] = ;
for(i = ; i < n ;i++)
{
for(j = ;j < sz; j++)
{
for(g = ;g < child_num ; g++)
{
if(val[ch[j][g]]) continue;
int o = ;
if(po[g]!=s[i]) o = ;
dp[i+][ch[j][g]] = min(dp[i+][ch[j][g]],dp[i][j]+o);
}
}
}
int ans = INF;
for(i = ;i < sz ; i++)
ans = min(ans,dp[n][i]);
printf("Case %d: ",kk);
if(ans==INF)
puts("-1");
else
printf("%d\n",ans);
}
}ac;
int main()
{
int i,m,kk=;
ac.init();
while(scanf("%d",&m)&&m)
{
ac.reset();
for(i = ;i <= m ;i++)
{
scanf("%s",vir);
ac.insert(vir,);
}
ac.construct();
scanf("%s",s);
int k = strlen(s);
ac.work(k,++kk);
}
return ;
}