题意：给定 n 个子串，然后给一个母串，让你对母串重排，然后问你最多含有多少个字串。
析：这个题很容易想到五维DP，这样的话，不但会MLE，而且连数组都不一定开的出来，里面有大量的无用的状态，所以我们把那四个字符出现的次数进行重新编制，假设A出现 a 次，C出现 c 次，G出现 g 次，T出现 t 次，进行压缩的时候，把第A的系数乘以((b+1) + (c+1) + (d+1))，C乘以((c+1) + (d+1))，G乘以(d+1)，T乘以1。这样就很简单的dp[i][j] 表示在 i 这个结点 j 状态时，最多有多少个。
代码如下：
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <cstring>
#include <set>
#include <queue>
#include <algorithm>
#include <vector>
#include <map>
#include <cctype>
#include <cmath>
#include <stack>
#include <sstream>
#include <list>
#include <assert.h>
#include <bitset>
#define debug() puts("++++");
#define gcd(a, b) __gcd(a, b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define fi first
#define se second
#define pb push_back
#define sqr(x) ((x)*(x))
#define ms(a,b) memset(a, b, sizeof a)
//#define sz size()
#define pu push_up
#define pd push_down
#define cl clear()
#define all 1,n,1
#define FOR(i,x,n) for(int i = (x); i < (n); ++i)
#define freopenr freopen("in.txt", "r", stdin)
#define freopenw freopen("out.txt", "w", stdout)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const double inf = 1e20;
const double PI = acos(-1.0);
const double eps = 1e-8;
const int maxn = 11*11*11*11 + 10;
const int maxm = 1e5 + 10;
const int mod = 50007;
const int dr[] = {-1, 0, 1, 0};
const int dc[] = {0, -1, 0, 1};
const char *de[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"};
int n, m;
const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
inline bool is_in(int r, int c) {
return r >= 0 && r < n && c >= 0 && c < m;
}
const int maxnode = 50 * 10 + 10;
const int sigma = 4;
int dp[maxnode][maxn];
struct Aho{
int ch[maxnode][sigma];
int f[maxnode];
int val[maxnode];
int sz;
void clear(){ sz = 1; ms(ch[0], 0); }
inline int idx(char ch){
if(ch == 'A') return 0;
if(ch == 'C') return 1;
if(ch == 'G') return 2;
return 3;
}
void insert(const char *s){
int u = 0;
for(int i = 0; s[i]; ++i){
int c = idx(s[i]);
if(!ch[u][c]){
ms(ch[sz], 0);
val[sz] = 0;
ch[u][c] = sz++;
}
u = ch[u][c];
}
++val[u];
}
void getFail(){
queue<int> q; f[0] = 0;
for(int i = 0; i < sigma; ++i){
int u = ch[0][i];
if(u){ f[u] = 0; q.push(u); }
}
while(!q.empty()){
int r = q.front(); q.pop();
for(int c = 0; c < sigma; ++c){
int u = ch[r][c];
if(!u){ ch[r][c] = ch[f[r]][c]; continue; }
q.push(u);
int v = f[r];
while(v && !ch[v][c]) v = f[v];
f[u] = ch[v][c];
val[u] += val[f[u]];
}
}
}
int solve(int s1, int s2, int s3, int s4){
ms(dp, -1); dp[0][0] = 0;
int cnt1 = s2 * s3 * s4;
int cnt2 = s3 * s4;
int cnt3 = s4;
int ans = 0;
FOR(j, 0, s1) FOR(k, 0, s2)
FOR(l, 0, s3) FOR(y, 0, s4) FOR(i, 0, sz){
int pre = j * cnt1 + k * cnt2 + l * cnt3 + y;
if(dp[i][pre] < 0) continue;
if(j + 1 < s1){
int nxt = ch[i][0];
int st = pre + cnt1;
dp[nxt][st] = max(dp[nxt][st], dp[i][pre] + val[nxt]);
ans = max(ans, dp[nxt][st]);
}
if(k + 1 < s2){
int nxt = ch[i][1];
int st = pre + cnt2;
dp[nxt][st] = max(dp[nxt][st], dp[i][pre] + val[nxt]);
ans = max(ans, dp[nxt][st]);
}
if(l + 1 < s3){
int nxt = ch[i][2];
int st = pre + cnt3;
dp[nxt][st] = max(dp[nxt][st], dp[i][pre] + val[nxt]);
ans = max(ans, dp[nxt][st]);
}
if(y + 1 < s4){
int nxt = ch[i][3];
int st = pre + 1;
dp[nxt][st] = max(dp[nxt][st], dp[i][pre] + val[nxt]);
ans = max(ans, dp[nxt][st]);
}
}
return ans;
}
};
Aho aho;
char s[50];
int main(){
int kase = 0;
while(scanf("%d", &n) == 1 && n){
aho.cl;
for(int i = 0; i < n; ++i){
scanf("%s", s);
aho.insert(s);
}
aho.getFail();
scanf("%s", s);
int cnt[4] = {1, 1, 1, 1};
for(int i = 0; s[i]; ++i)
++cnt[aho.idx(s[i])];
printf("Case %d: %d
", ++kase, aho.solve(cnt[0], cnt[1], cnt[2], cnt[3]));
}
return 0;
}