能AC还是很开心的...此题没有POJ2778那么难，那个题还需要矩阵乘法，两个题有点相似的。
做题之前，把2778代码重新看了一下，回忆一下当时做题的思路，回忆AC自动机是干嘛的...
状态表示dp[i][j]长度为i的以j串为结束的最小改变数目。AC自动机预处理一下，然后DP。
卡内存+不知道状态数，MLE+RE+WA了多次。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstdlib>
using namespace std;
#define N 2222222
#define INF 10000000
int trie[N][];
int o[N];
int que[N];
int fail[N];
int dp[][];
int t;
void CL()
{
memset(trie,-,sizeof(trie));
memset(o,,sizeof(o));
t = ;
}
int judge(char s)
{
switch(s)
{
case'A':return ;
case'C':return ;
case'G':return ;
case'T':return ;
}
return ;
}
void insert(char *str)
{
int i,len,root;
root = ;
len = strlen(str);
for(i = ;i < len;i ++)
{
if(trie[root][judge(str[i])] == -)
trie[root][judge(str[i])] = t ++;
root = trie[root][judge(str[i])];
}
o[root] = ;
}
void build_ac()
{
int head,tail,front,i;
head = tail = ;
for(i = ;i < ;i ++)
{
if(trie[][i] != -)
{
fail[trie[][i]] = ;
que[tail++] = trie[][i];
}
else
{
trie[][i] = ;
}
}
while(head != tail)
{
front = que[head++];
if(o[fail[front]])
o[front] = ;
for(i = ;i < ;i ++)
{
if(trie[front][i] != -)
{
que[tail++] = trie[front][i];
fail[trie[front][i]] = trie[fail[front]][i];
}
else
{
trie[front][i] = trie[fail[front]][i];
}
}
}
}
int main()
{
int n,i,j,k,len,flag,cas = ;
char str[];
while(scanf("%d",&n)!=EOF)
{
if(n == ) break;
CL();
for(i = ;i <= n;i ++)
{
scanf("%s",str);
insert(str);
}
build_ac();
scanf("%s",str);
len = strlen(str);
for(i = ;i <= len;i ++)
{
for(j = ;j <= t;j ++)
dp[i][j] = INF;
}
dp[][] = ;
for(i = ;i < len;i ++)
{
for(j = ;j < t;j ++)
{
if(o[j]) continue;
for(k = ;k < ;k ++)
{
if(o[trie[j][k]]) continue;
flag = !(k == judge(str[i]));
dp[i+][trie[j][k]] = min(dp[i+][trie[j][k]],dp[i][j] + flag);
}
}
}
int ans = INF;
for(i = ;i < t;i ++)
{
ans = min(ans,dp[len][i]);
}
printf("Case %d: ",cas ++);
if(ans == INF)
printf("-1\n");
else
printf("%d\n",ans);
}
return ;
}