开始肝这道题的时候也是冒了十足的勇气……呜呜呜，当时一直没发现，我有个地方写成了"s[i] - 'A'"，怎么能这样用啊！毕竟只有A、C、G、T的说……呜呜呜…… QAQ
然后讲一下，这道题的AC自动机的想法，还有DP的思路（我DP超菜…… 能过也是超神了……），我们在这用AC自动机来做的是去取状态，那么怎么取状态？我们先按照普遍的写法（AC自动机上建满路，下一步到达A、C、G、T全都要），然后去推前一刻的状态，用dp[0][0]表示0初始状态，然后去不断的往下递推待查询的那个模式串，要求是这样的，如果遇到的是病毒感染状态，那么就是不能要的状态，就不去更新它了（故除0初始状态以外，都赋为最大值点），如果目前不是病毒状态，我们去看，它可以改变成除了它以外的另外的状态（不一定是满的3个，因为有可能会从健康态变成病毒态），然后，若是改变原先的字符串，就要在之前的那一步上"+1"，多了一步改变；若是发现是相等的，那么就不需要改变，去取最小值即可（因为可能存在不同的状态递推到这个点的状态）。
然后AC自动机上怎么写？我们存储全部的状态，包括那些个不在字符串上的额外的状态，然后用一个静态数组去存它们，大致会有最多1000组的状态吧，把状态记录下来，然后在DP的时候去用到就可以了，主要是反映出前一刻的状态之用（此时的AC自动机的主要用途）。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdlib>
#include <ctime>
#include <unordered_map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int maxN = 1005;
unordered_map<char, int> dir;
inline void pre_did() { dir['A'] = 0; dir['C'] = 1; dir['G'] = 2; dir['T'] = 3; }
int N, num, dp[maxN][maxN], ans;
char virus[55], test[maxN];
struct node
{
node *next[4];
node *fail;
int flag, id;
node()
{
for(int i=0; i<4; i++) next[i] = NULL;
fail = NULL;
flag = id = 0;
}
}tree[maxN];
node *root;
node *new_node()
{
node *p = &tree[num];
for(int i=0; i<4; i++) p->next[i] = NULL;
p->fail = NULL;
p->flag = 0;
p->id = num++;
return p;
}
void update(char *s)
{
node *temp = root;
int len = (int)strlen(s);
for(int i=0; i<len; i++)
{
int x = dir[s[i]];
if(temp->next[x] == NULL) temp->next[x] = new_node();
temp = temp->next[x];
}
temp->flag = 1;
}
void build_fail()
{
queue<node *> Q;
Q.push(root);
node *temp;
while(!Q.empty())
{
temp = Q.front(); Q.pop();
for(int i=0; i<4; i++)
{
if(temp->next[i])
{
if(temp == root) temp->next[i]->fail = root;
else
{
node *p = temp->fail;
while(p)
{
if(p->next[i]) { temp->next[i]->fail = p->next[i]; break; }
p = p->fail;
}
if(!p) temp->next[i]->fail = root;
if(temp->next[i]->fail->flag) temp->next[i]->flag = 1;
}
Q.push(temp->next[i]);
}
else temp->next[i] = (temp == root ? root : temp->fail->next[i]);
}
}
}
void AC_auto(char *s)
{
ans = INF; memset(dp, INF, sizeof(dp));
dp[0][0] = 0;
int len = (int)strlen(s);
for(int i=0; i<len; i++)
{
for(int j=0; j<num; j++)
{
for(int k=0; k<4; k++)
{
if(tree[j].next[k]->flag) continue;
int x = dir[s[i]];
if(x == k)
{
dp[i+1][tree[j].next[k]->id] = min(dp[i][j], dp[i+1][tree[j].next[k]->id]);
}
else
{
dp[i+1][tree[j].next[k]->id] = min(dp[i][j] + 1, dp[i+1][tree[j].next[k]->id]);
}
}
}
}
for(int i=0; i<num; i++) ans = min(ans, dp[len][i]);
if(ans >= INF) ans = -1;
}
inline void init()
{
num = 0;
root = new_node();
}
int main()
{
pre_did();
int Cas = 0;
while(scanf("%d", &N) && N)
{
init();
for(int i=1; i<=N; i++)
{
scanf("%s", virus);
update(virus);
}
build_fail();
scanf("%s", test);
AC_auto(test);
printf("Case %d: %d\n", ++Cas, ans);
}
return 0;
}
