|
|
 #include <iostream>
#include <math.h>
using namespace std;
const int MAXN=20*55;
const int MAXL=1005;
const int K=4;// kind of child
int dp[MAXL][MAXN];
struct Node
   {
 Node *next[K], *fail;
int flag, id; // use for T[j].next[k]->id
void Init(int index)
  {
id=index;
flag=0;
fail=NULL;
for(int i=0; i<K; i++)next[i]=NULL;
 }
 }* Q[MAXN/2], *root, T[MAXN];// Q for queue, root&T for tree;
int index=0;
Node * newNode()
{
T[index].Init(index);
return &T[index++];
}
int tokind(char k)
{
if(k=='A')return 0;
else if(k=='C')return 1;
else if(k=='G')return 2;
else return 3;
}
void insert(char *str)
{
if(root==NULL)
root=newNode();
Node *now=root;
for(int i=0; str[i]; i++)
{
int kind=tokind(str[i]);
if(now->next[kind]==NULL)
now->next[kind]=newNode();
now=now->next[kind];
}
now->flag=1;
}
int search(Node *p)
{
while(p!=root)
{
p=p->fail;
if(p->flag)return 1;
}
return 0;
}
void buildAC()
{
int head=0, tail=0;
root->fail=NULL;
Q[tail++]=root;
while(head<tail)
{
Node *now=Q[head++];
if(now->flag==0)now->flag=search(now);
for(int i=0; i<K; i++)
{
if(now->next[i]!=NULL)
{
if(now==root)
now->next[i]->fail=root;
else
now->next[i]->fail=now->fail->next[i];
Q[tail++]=now->next[i];
}
else
{
if(now==root)
now->next[i]=root;
else
now->next[i]=now->fail->next[i];
}
}
}
}
void update(int &a, int b){if(a==-1||b<a)a=b;}
int slove(char *str)
{
memset(dp, -1, sizeof(dp));
dp[0][0]=0;
Node *p=root;
for(int i=0; str[i]; i++)
{
for(int j=0; j<index; j++)
{
if(dp[i][j]!=-1&&T[j].flag==0)
{
int kind=tokind(str[i]);
for(int k=0; k<K; k++)// need to match (k, kind)
{
Node *chd=T[j].next[k];
if(chd->flag==0)
update(dp[i+1][chd->id],dp[i][j]+(k!=kind));
}
}
}
}
int len=strlen(str);
int res=-1;
for(int ii=0; ii<index; ii++)
if(dp[len][ii]!=-1)update(res, dp[len][ii]);
return res;
}
int main()
{
freopen ("in.txt", "r", stdin);
int N, Tcase=0;
while(scanf("%d", &N)!=EOF&&N)
{
root=NULL;
index=0;
for(int i=0; i<N; i++)
{
char s[25];
scanf("%s", s);
insert(s);
}
buildAC();
char ss[1005];
scanf("%s", ss);
printf("Case %d: %d\n", ++Tcase, slove(ss));
}
return 0;
}
|