题意：容易理解...
思路：首先一开始容易想到要用到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!='\0';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]!='\0';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\n",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;}