类似的dp省赛时就做过了，不过这题卡内存，需要把当前状态hash一下，可以按进制来算出当前的状态，因为所有的状态数是不会超过10*10*10*10的，所以完全可以把这些存下来。
刚开始把trie的的遍历节点写在外层循环了，一直WA，后来想了一下，状态是只会向前走的，但是节点不一样，如果由 当前节点的状态-》下一节点的状态，下一节点有可能是在当前节点之前的，这样是不对的，所以需要由当前状态的节点 -》下一状态的节点 。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 510
#define LL long long
#define INF -1
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
const int child_num = ;
char vir[],s[];
int mp[];
class AC
{
private:
int ch[N][child_num];
int Q[N];
int fail[N];
int val[N];
int id[];
int sz;
int dp[N][];
public:
void init()
{
fail[] = ;
id['A'] = ,id['G'] = ,id['T'] = ,id['C'] = ;
}
void reset()
{
memset(ch[],,sizeof(ch[]));
memset(val,,sizeof(val));
sz = ;
}
void insert(char *a,int key)
{
int p = ;
for( ; *a ; a++)
{
int d = id[*a];
if(ch[p][d]==)
{
memset(ch[sz],,sizeof(ch[sz]));
ch[p][d] = sz++;
}
p = ch[p][d];
}
val[p] += key;
}
void construct()
{
int i,head=,tail = ;
for(i = ;i < child_num ; i++)
{
if(ch[][i])
{
fail[ch[][i]] = ;
Q[tail++] = ch[][i];
}
}
while(head!=tail)
{
int u = Q[head++];
val[u]+=val[fail[u]];
for(i = ; i < child_num ; i++)
{
if(ch[u][i])
{
fail[ch[u][i]] = ch[fail[u]][i];
Q[tail++] = ch[u][i];
}
else ch[u][i] = ch[fail[u]][i];
}
}
}
void work(char *s,int kk)
{
int k = strlen(s);
int num[]= {},pp[];
memset(num,,sizeof(num));
int o = ,i,j,g,e,z,y;
for(i = ; i < k ;i++)
{
num[id[s[i]]]++;
}
pp[] = ;
for(i = ; i <= ; i++)
pp[i] = pp[i-]*;
memset(mp,-,sizeof(mp));
for(i = ; i <= num[] ; i++)
for(j = ;j <= num[] ; j++)
for(g = ; g <= num[] ; g++)
for(e = ; e <= num[] ;e++)
{
int sum = e*pp[]+g*pp[]+j*+i;
o++;
mp[sum] = o;
}
memset(dp,-,sizeof(dp));
dp[][] = ;
for(i = ; i <= num[] ; i++)
for(j = ;j <= num[] ; j++)
for(g = ; g <= num[] ; g++)
for(e = ; e <= num[] ;e++)
{
for(z = ;z < sz ; z++)
{
int sum = e*pp[]+g*pp[]+j*+i;
if(dp[z][mp[sum]]==-) continue;
for(y = ; y < child_num ; y++)
{
int yy = ch[z][y];
int ss = pp[y]+sum;
if(mp[ss]==-) continue;
dp[yy][mp[ss]] = max(dp[yy][mp[ss]],dp[z][mp[sum]]+val[yy]);
}
}
}
int ans = ;
for(i = ;i < sz ; i++)
{
ans=max(dp[i][o],ans);
}
printf("Case %d: ",kk);
printf("%d\n",ans);
}
}ac;
int main()
{
int n,kk=;
ac.init();
while(scanf("%d",&n)&&n)
{
ac.reset();
kk++;
while(n--)
{
scanf("%s",vir);
ac.insert(vir,);
}
ac.construct();
scanf("%s",s);
ac.work(s,kk);
}
return ;
}