学了编译原理的自动机后理解起来容易多了，对于一个字符串我只关心最后几个字符组成的前缀是AC自动机中的哪个状态节点，然后在AC自动机上进行转移。
我们可以先构造一个AC自动机，然后把各个节点之间的合法联系做成矩阵，这样就方便后面查询了。
需要注意的地方：
1、判断一个节点是否合法，除了看自身外还要看其父节点和其fail指向的第一个节点。（考虑到子串包含的原因）
2、打合法关系表时，打出合法关系要保证出发点和到达点都是合法的。
3、针对这题我的代码来说，DP过程要注意最后i==len,也就是处理DP[S.length()][j]时，要特殊判断一下，因为已经不能继续更新了，目测用优先队列写就不会出现这问题，因为第一次访问到DP[S.lenth()][j]时就可以直接返回答案了。
PS：算上调试代码，266行，敲的时候感觉有点儿畏首畏尾，生怕哪出点儿问题，若是加上比赛时压力，以我目前的水平，我觉得比赛时我是敲不出来的...
代码如下：
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
#define maxc 4
#define INF 0x7fffffff
int ACCnt;
int Trans[2005][5];//记录AC自动机上的状态转移
//bool IsBad[2005];
struct Node
{
char ch;
int id;
bool is; //记录当前节点是否非法，由父节点以及各个fail节点决定
Node *child[maxc];
Node *fail;
Node ()
{
ch=' ';
id=ACCnt++;
is=false;
for(int i=0;i<maxc;++i)
{
child[i]=NULL;
}
fail=NULL;
}
Node (char c)
{
ch=c;
id=ACCnt++;
is=false;
for(int i=0;i<maxc;++i)
{
child[i]=NULL;
}
fail=NULL;
}
};
Node *Root;
void Init()
{
ACCnt=0;
memset(Trans,-1,sizeof(Trans));
// memset(IsBad,false,sizeof(IsBad));
Root=new Node();
}
int ID(char c)
{
if(c=='A')
return 0;
if(c=='T')
return 1;
if(c=='C')
return 2;
if(c=='G')
return 3;
}
void Insert(char chs[])
{
// cout<<"entry"<<endl;
int i,id,len=strlen(chs);
char c;
Node *t=Root;
for(i=0;i<len;++i)
{
c=chs[i];
id=ID(c);
// cout<<i<<" "<<c<<" "<<id<<endl;
if(t->child[id]==NULL)
t->child[id]=new Node(c);
t=t->child[id];
}
t->is=true;
}
void DeleteTrie(Node *t)
{
int i;
for(i=0;i<maxc;++i)
{
if(t->child[i]!=NULL)
DeleteTrie(t->child[i]);
}
delete t;
}
void PreAC()
{
// cout<<"AC"<<endl;
queue<Node*> q;
q.push(Root);
int i;
Node *p,*t;
while(!q.empty())
{
p=q.front();
q.pop();
// if(p->is)
// IsBad[p->id]=true;
// cout<<p->id<<" "<<p->is<<endl;
for(i=0;i<maxc;++i)
{
if(p->child[i]!=NULL)
{
// cout<<p->child[i]->id<<endl;
t=p->fail;
while(t!=NULL&&t->child[i]==NULL)
t=t->fail;
if(t==NULL)
p->child[i]->fail=Root;
else
p->child[i]->fail=t->child[i];
p->child[i]->is|=((p->is)|(p->child[i]->fail->is));
q.push(p->child[i]);
}
}
}
}
void PreTrans()
{
queue<Node*> q;
q.push(Root);
int i;
Node *p,*t;
while(!q.empty())
{
p=q.front();
q.pop();
if(p->is)
continue;
for(i=0;i<maxc;++i)
{
if(p->child[i]!=NULL)
q.push(p->child[i]);
t=p;
while(t!=NULL&&t->child[i]==NULL)
t=t->fail;
if(t==NULL)
t=Root;
else
t=t->child[i];
if(!(t->is))
Trans[p->id][i]=t->id;
}
}
}
void Show()
{
int i,j;
for(i=0;i<ACCnt;++i)
{
cout<<i<<":";
for(j=0;j<maxc;++j)
cout<<" "<<Trans[i][j];
cout<<endl;
}
}
string S;
int DP[1005][2005];
bool Inq[1005][2005];
int Work()
{
memset(DP,-1,sizeof(DP));
memset(Inq,false,sizeof(Inq));
DP[0][0]=0;
queue<int> q1,q2;
q1.push(0),q2.push(0);
Inq[0][0]=true;
int i,len,state,state2,val;
// cout<<"Work init complete"<<endl;
while(!q1.empty())
{
len=q1.front(),state=q2.front();
q1.pop(),q2.pop();
// cout<<"len: "<<len<<" "<<"state: "<<state<<endl;
Inq[len][state]=false;
if(len==S.length())
continue;
for(i=0;i<maxc;++i)
{
if(Trans[state][i]==-1)
continue;
state2=Trans[state][i];
// cout<<"new state: "<<state2<<endl;
if(DP[len+1][state2]==-1)
DP[len+1][state2]=DP[len][state]+(ID(S[len])!=i);
else
DP[len+1][state2]=min(DP[len+1][state2],DP[len][state]+(ID(S[len])!=i));
if(!Inq[len+1][state2])
{
Inq[len+1][state2]=true;
q1.push(len+1),q2.push(state2);
}
}
}
int ans=INF;
len=S.length();
for(i=0;i<ACCnt;++i)
if(DP[len][i]!=-1)
ans=min(ans,DP[len][i]);
return ans;
}
int main()
{
int n,i,ans,cas=0;
char chs[25];
while(scanf("%d",&n)!=EOF)
{
if(n==0)
break;
cas++;
Init();
// cout<<"Init complete"<<endl;
while(n--)
{
scanf("%s",chs);
Insert(chs);
// cout<<"Insert complete"<<endl;
}
PreAC();
// cout<<"PreAC complete"<<endl;
PreTrans();
// cout<<"PreTrans complete"<<endl;
// cout<<"State number: "<<ACCnt<<endl;
// Show();
cin>>S;
ans=Work();
if(ans==INF)
printf("Case %d: -1\n",cas);
else
printf("Case %d: %d\n",cas,ans);
DeleteTrie(Root);
}
return 0;
}
/*int Find(char T[])
{
int i,id,ans=0,len=strlen(T);
Node *p,*t;
p=Root;
char c;
for(i=0;i<len;++i)
{
c=T[i];
id=c-'a';
while(p!=NULL&&p->child[id]==NULL)
p=p->fail;
if(p==NULL)
p=Root;
else
{
p=p->child[id];
t=p;
while(t!=NULL)
{
if(t->is)
ans++;
t=t->fail;
}
}
}
return ans;
}*/