题意：容易理解...
思路：首先一开始容易想到要用到dp，开设一个dp[41][41][41][41][501]的数组来解决，但是明显内存已经超出范围了，于是就想如何减少内存呢？只要知道A、T、C、G其中三个的个数，则另一个也能算出，于是空间可以缩小到：41*41*41*500，但是还是不行啊！想了好久还是没找到方法，于是就问了一个大神，他的一个提示给了我灵感：虽然A、T、C、G的个数范围是[0,40]，但是numa+numc+numg+numt的范围也是[0,40]，于是就可以推出numa*numc*numg*numt的范围为[0,15000]（自己写四个for循环可以算出最大为13000多），于是就可以压缩成一个dp[15000][501]的数组了。后来看了网上的方法，他们用了什么变进制，我表示现在还没看懂！！
代码实现：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
#include<queue>
using namespace std;
struct node{
int next[4];
int fail;
int num;
void init()
{
memset(next,0,sizeof(next));
fail=0;
num=0;
}
}a[505];
int tot,n;
int hash[41][41][41][41];
int ta,tc,tg,tt;
int dp[15000][505];
char keyword[15];
char S[45];
int MAX(int a,int b)
{
return a>b?a:b;
}
void chushihua()
{
memset(dp,-1,sizeof(dp));
ta=tc=tg=tt=0;
tot=0;
a[0].init();
}
int hash1(char x)
{
if(x=='A')
return 0;
else if(x=='C')
return 1;
else if(x=='G')
return 2;
else
return 3;
}
void insert(char *str)//建立字典树
{
int index,p=0;
for(;*str!=' ';str++)
{
index=hash1(*str);
if(a[p].next[index]==0)
{
a[++tot].init();
a[p].next[index]=tot;
}
p=a[p].next[index];
}
a[p].num++;
}
void build_ac()//建立trie图
{
int i,p,cur,son;
queue<int>Q;
Q.push(0);
while(!Q.empty())
{
p=Q.front();
Q.pop();
for(i=0;i<4;i++)
{
if(a[p].next[i]!=0)
{
son=a[p].next[i];
cur=a[p].fail;
if(p==0)
a[son].fail=0;
else
{
while(cur&&a[cur].next[i]==0)
cur=a[cur].fail;
a[son].fail=a[cur].next[i];
}
if(a[a[son].fail].num)
a[son].num+=a[a[son].fail].num;
Q.push(son);
}
else
a[p].next[i]=a[a[p].fail].next[i];
}
}
}
void yasuo()//进行压缩
{
int i,j,k,l,num=0;
for(i=0;S[i]!=' ';i++)
if(S[i]=='A')
ta++;
else if(S[i]=='C')
tc++;
else if(S[i]=='G')
tg++;
else
tt++;
for(i=0;i<=ta;i++)
for(j=0;j<=tc;j++)
for(k=0;k<=tg;k++)
for(l=0;l<=tt;l++)
hash[i][j][k][l]=num++;
}
void solve(int zuhao)
{
int i,j,k,l,p,q,son,x1,x2,max=0;
dp[0][0]=0;
for(i=0;i<=ta;i++)
for(j=0;j<=tc;j++)
for(k=0;k<=tg;k++)
for(l=0;l<=tt;l++)
{
if(i+j+k+l==0)
continue;
x1=hash[i][j][k][l];//解压
for(p=0;p<=tot;p++)
{
for(q=0;q<4;q++)
{
if(q==0&&i-1>=0)
x2=hash[i-1][j][k][l];
else if(q==1&&j-1>=0)
x2=hash[i][j-1][k][l];
else if(q==2&&k-1>=0)
x2=hash[i][j][k-1][l];
else if(q==3&&l-1>=0)
x2=hash[i][j][k][l-1];
else
continue;
if(dp[x2][p]==-1)
continue;
son=a[p].next[q];
dp[x1][son]=MAX(dp[x1][son],dp[x2][p]+a[son].num);
if(dp[x1][son]>max)
max=dp[x1][son];
}
}
}
printf("Case %d: ",zuhao);
printf("%d
",max);
}
int main()
{
int zuhao=0;
while(scanf("%d",&n)!=EOF&&n)
{
zuhao++;
chushihua();
getchar();
while(n--)
{
scanf("%s",keyword);
insert(keyword);
}
build_ac();
scanf("%s",S);
yasuo();
solve(zuhao);
}
return 0;
}