题意：给出一些不合法的模式DNA串，给出一个原串，问最少需要修改多少个字符，使得原串中不包含非法串。
解题关键：多模式串匹配->AC自动机，求最优值->dp，注意在AC自动机上dp的套路。
AC自动机上的每个节点其实就是一种状态，进行模式匹配其实就是进行边的匹配
令$dp[i][j]$表示字符串长度为$i$时到达AC自动机上某个状态所需要修改的最小值。
转移方程：$dp[i + 1][Next[j][k]] = \min (dp[i][j] + (k! = str[i]),dp[i + 1][Next[j][k]])$
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<queue>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N=;
const int MAXN=;
ll m,n;
int dp[][MAXN];
struct Trie{
int Next[MAXN][N],Fail[MAXN],root,tot;
bool End[MAXN];
int newnode(){
for(int i=;i<N;i++) Next[tot][i]=-;
End[tot++]=false;
return tot-;
}
void init(){
tot=;
root=newnode();
}
void insert(char buf[]){
int len=strlen(buf),now=root,k;
for(int i=;i<len;i++){
if(buf[i]=='A') k=;
else if(buf[i]=='G') k=;
else if(buf[i]=='C') k=;
else k=;
if(Next[now][k]==-) Next[now][k]=newnode();
now=Next[now][k];
}
End[now]=true;
}
void build(){
queue<int>que;
Fail[root]=root;
for(int i=;i<N;i++){
if(Next[root][i]==-) Next[root][i]=root;
else{
Fail[Next[root][i]]=root;
que.push(Next[root][i]);
}
}
while(!que.empty()){
int now=que.front();
que.pop();
if(End[Fail[now]]) End[now]=true;
for(int i=;i<N;i++){
if(Next[now][i]==-) Next[now][i]=Next[Fail[now]][i];//Next指针都已经建立好
else{
Fail[Next[now][i]]=Next[Fail[now]][i];
que.push(Next[now][i]);
}
}
}
}
int solve(char buf[]){
int len=strlen(buf);
for(int i=;i<=len;i++) for(int j=;j<=tot;j++) dp[i][j]=inf;
dp[][]=;
for(int i=;i<len;i++){//最主要的事情就是分清边和点
int tmp;
if(buf[i]=='A') tmp=;
else if(buf[i]=='G') tmp=;
else if(buf[i]=='C') tmp=;
else tmp=;
for(int j=;j<tot;j++){
if(dp[i][j]==inf||End[j]) continue;
for(int k=;k<;k++){
int u=Next[j][k];
if(End[u]) continue;
dp[i+][u]=min(dp[i][j]+(tmp!=k),dp[i+][u]);
}
}
}
int ans=inf;
for(int i=;i<tot;i++) ans=min(ans,dp[len][i]);
return ans==inf?-:ans;
}
}; Trie ac;
char buf[];
int main(){
int ca=;
while(scanf("%d",&n)&&n){
ca++;
ac.init();
for(int i=;i<n;i++) scanf("%s",buf),ac.insert(buf);
ac.build();
scanf("%s",buf);
int ans=ac.solve(buf);
printf("Case %d: %d\n",ca,ans);
}
}