题目大意：先给你一些子串，然后给你一个母串，母串里面的字母可以任意调换位置，问最多这个母串经过一些位置变动最多能包含多少个子串。
分析：可以比较明显的看出来的DP，先求出来ATGC分别有多少，然后再处理，不过有个比较麻烦的地方，因为ATGC的字母数最多是40，因为不知道那种字母所以是40*40*40*40,很明显这种复杂度太高，开始使用了一次打标，把每种状态都保存下来，并且保存它的下一个状态，不过很不幸这种方法TLE了，因为找他的下一个状态不是太容易，看了大神的题解后明白，其实可以使用4种不同的进制来做，进制数就是这个碱基数的总个数，这样复杂度很明显就降低了，而且状态再转移的时候也很容易。
代码如下：
===================================================================================================================================
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std; const int MAXN = ;
const int MaxSon = ;
const int oo = 1e9; int Find(char ch)
{
if(ch == 'A')return ;
if(ch == 'T')return ;
if(ch == 'G')return ; return ;
}
struct Ac_Trie
{
int next[][];
int Fail[], End[];
int root, cnt; int newnode()
{
for(int i=; i<MaxSon; i++)
next[cnt][i] = -;
Fail[cnt] = End[cnt] = false; return cnt++;
}
void InIt()
{
cnt = ;
root = newnode();
}
void Insert(char s[])
{
int now = root; for(int i=; s[i]; i++)
{
int k = Find(s[i]); if(next[now][k] == -)
next[now][k] = newnode();
now = next[now][k];
} End[now] += ;
}
void GetFail()
{
int now = root;
queue<int> Q; for(int i=; i<MaxSon; i++)
{
if(next[now][i] == -)
next[now][i] = root;
else
{
Fail[next[now][i]] = root;
Q.push(next[now][i]);
}
} while(Q.size())
{
now = Q.front();
Q.pop(); for(int i=; i<MaxSon; i++)
{
if(next[now][i] == -)
next[now][i] = next[Fail[now]][i];
else
{
Fail[next[now][i]] = next[Fail[now]][i];
Q.push(next[now][i]);
}
} End[now] += End[Fail[now]];
}
}
};
struct ATGC
{
int sum[], bit[];
int dp[][MAXN];
Ac_Trie ac; void GetSum(char s[])
{
memset(sum, , sizeof(sum));
memset(bit, , sizeof(bit)); for(int i=; s[i]; i++)
{
int k = Find(s[i]);
sum[k]++;
}
}
void GetBit()
{
bit[] = (sum[]+)*(sum[]+)*(sum[]+);
bit[] = (sum[]+)*(sum[]+);
bit[] = sum[]+;
bit[] = ;
}
int GetDp()
{
memset(dp, -, sizeof(dp));
dp[][] = ; int ans = ; for(int A=; A<=sum[]; A++)
for(int T=; T<=sum[]; T++)
for(int G=; G<=sum[]; G++)
for(int C=; C<=sum[]; C++)
{
int k = A*bit[] + T*bit[] + G*bit[] + C*bit[]; for(int i=; i<ac.cnt; i++)
{
if(dp[i][k] == -)continue; for(int j=; j<MaxSon; j++)
{
if(j == && A==sum[])continue;
if(j == && T==sum[])continue;
if(j == && G==sum[])continue;
if(j == && C==sum[])continue; int next = ac.next[i][j];
int nextk = k + bit[j]; dp[next][nextk] = max(dp[next][nextk], dp[i][k]+ac.End[next]);
ans = max(ans, dp[next][nextk]);
}
}
} return ans;
}
}; ATGC a; int main()
{
int i, N, t=; while(scanf("%d", &N), N)
{
char s[];
a.ac.InIt(); for(i=; i<N; i++)
{
scanf("%s", s);
a.ac.Insert(s);
}
a.ac.GetFail(); scanf("%s", s); a.GetSum(s);
a.GetBit(); int ans = a.GetDp(); printf("Case %d: %d\n", t++, ans);
} return ;
}