poj3691(DNA Repair)

/*
AC自动机，增设虚拟节点,求长度为n的字符串中包含至少k个给出的关键字的字符串的个数，结果模MOD。
增设虚拟节点的目的是为了方便状态转移。
dp转移实际上是在安全图上进行的！
*/
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
const int N= 55*20; //节点个数的最大值
const int S=4; //不同的字符 个数
const int MOD=20090717;
const int LEN=1005; //n的最大值
struct node{
	node *sons[S], *fail;
	int id; //id是节点的标号
	bool flag; //标记该节点是否是安全的
}nodes[N], *root;
int cnt;  //cnt是树中节点的 个数
node *que[N];
int n, m, k;
int dp[2][N];
map<char, int> mci;
map<int, char> mic;
char str[LEN];
void init(){
	mci['A']=0; mic[0]='A';
	mci['G']=1; mic[1]='G';
	mci['C']=2; mic[2]='C';
	mci['T']=3; mic[3]='T';
}
void clear(){
	cnt=0;
	root=NULL;
}
node* newNode(){
	node* ans=&nodes[cnt];
	memset(ans->sons, 0, S*sizeof(node*));
	ans->fail=NULL;
	ans->id=cnt++;
	ans->flag=true;
	return ans;
}
int hash(char ch){ //字符的哈希函数，根据不同的需要而定
	return mci[ch];
}
//j表示当前关键字的标号
void insert(node*& root, char* str){
	node* t=root;
	int i, k;
	for(i=0; str[i]; i++){
		if(t->sons[k=hash(str[i])]==NULL){
			t->sons[k] = newNode();
		}
		t=t->sons[k];
	}
	t->flag=false;
}
//在某些时候还需要吧root的S个儿子节点中为空赋值为root（所谓的虚拟节点，树中的 其他节点也可以
//添加类似的虚拟节点）
void getFail(node*& root){
	int l, r, i;
	node *t;
	l=r=0;
	root->fail=root; //这样可以保证每个节点的fail指针都是非空的
	for(que[r++]=root; l!=r; ){
		t=que[l++];
		for(i=0; i<S; i++){
			if(t->sons[i]){
				que[r++]=t->sons[i];
				if(t==root){
					t->sons[i]->fail=t;
				}else{
					t->sons[i]->fail=t->fail->sons[i];
				}
				if(!t->sons[i]->fail->flag){
					t->sons[i]->flag=false;
				}
			}else{ //增设虚拟节点
				if(t==root) t->sons[i]=t;
				else t->sons[i]=t->fail->sons[i];
			}
		}
	}
}
bool input(){
	int n;
	scanf("%d", &n);
	if(n==0)return false;
	int i;
	char s[25];
	clear();
	root=newNode();
	for(i=0; i<n; i++){
		scanf("%s", s);
		insert(root, s);
	}
	return true;
}
int ca=0;
void solve(){
	getFail(root);
	int u, v, i, j, k, nxt, tmp;
	for(i=0; i<cnt; i++){
		dp[0][i]=-1;
	}
	dp[0][0]=0;
	scanf("%s", str);
	for(u=0, i=0; str[i]; i++){
		v=u^1;
		for(j=0; j<cnt; j++){
			dp[v][j]=-1;
		}
		for(j=0; j<cnt; j++){
			if(dp[u][j]==-1) continue;
			for(k=0; k<S; k++){
				if(!nodes[nxt=nodes[j].sons[k]->id].flag) continue;
				tmp = dp[u][j];
				if(str[i]!=mic[k]){
					tmp++;
				}
				if(dp[v][nxt]==-1 || dp[v][nxt]>tmp){
					dp[v][nxt]=tmp;
				}
			}
		}
		/*
		 *这里dp[v][k]表示长度为字符串str的前i个字符组成的子串走到节点k需要改变的最少次数,
		 *这个走到节点k可以这样来理解，该子串的后面部分等于节点k代表的字符串！例如子串为abbc，
		 *节点k代表的字符串是bb，那么该子串走到节点k的时候就成了abbb了，所以就容易理解为什么
		 *会有下面这一句了，因为要把最后一个字符c变成b！
		 *if(str[i]!=mic[k]){
			tmp++;
		  }
		 */
		u=v;
	}
	int ans=-1;
	for(j=0; j<cnt; j++){
		if(!nodes[j].flag) continue;
		if(dp[u][j]!=-1 && (ans==-1 || ans>dp[u][j])){
			ans=dp[u][j];
		}
	}
	printf("Case %d: %d\n", ++ca, ans);
}
int main(){
	//freopen("in.txt", "r", stdin);
	init();
	while(input()) solve();
	return 0;
}