题意 : 给出 n 个模式串，最后给出一个主串，问你主串打乱重组的情况下，最多能够包含多少个模式串。
分析 : 如果你做过类似 Trie图 || AC自动机 + DP 类似的题目的话，那么这道题相对之前的对于主串的“构造”过程加上了一个限制，那就是字符的元素的有限制的，那么DP的状态就不能用长度来表示状态（ 类比 POJ 2778 ），所以写出了一个错误的根据长度DP的代码
; i<len; i++){
; j<ac.Size; j++){
){
; k<; k++){
){///表示 i、j 状态下，0123代表的“ATGC”字符数还剩多少，但是这是错的，因为在长度为 i 停留在当前节点
///j 的字符串可能有多种，而这些字符串所拥有的剩余字符数是不一样的，不能单纯只用Lter[i][j][k]表示
///实际上这只是我自己的理解，我没有打表跟踪过错误数据，你可以自己想想为什么这样子不行……
;
int newj = ac.Node[j].Next[k];
dp[newi][newj] = max(dp[newi][newj], dp[i][j] + ac.Node[newj].cnt);
; l<; l++)
Lter[newi][newj][l] = Lter[i][j][l];
Lter[newi][newj][k]--;
}
}
}
}
}
那要如何定义DP状态呢？一般来说对于这样的数量和所在节点状态是关键点，所以我们可以DP[A][T][G][C][Node]前四维表示ATGC数量，最后一维表示当前状态停留在节点 Node ，但是这样子空间会爆炸，这时候就需要压缩一下状态，考虑压缩前四维，网上有很多利用进制的压缩，弱智的我有点不理解，所以还是用了普通的Hash，即利用一个四维数组 Hash[11][11][11][11] ( 每一个字母最多就是 10 个，所以这样开数组 ) ，然后只需要统计主串各个种类字符的数量，就能打出一个 Hash 表，将原本五维DP压成二维DP，DP[i][j] 表示各个字符数量状态为 i 且停留在 j 节点的最多包含模式串个数，则状态转移方程为 ( 一个节点状态能转到"ATGC"四个状态，那么以转到字符 ' A ' 为例 )
DP[ Hash[A+1][G][T][C] ][j] = max( DP[ Hash[A+1][G][T][C] ][j], DP[i][j] + Trie[j]['A'].cnt )
DP初始状态为 DP[0][0] = 0、DP[0~最大的Hash值数量][0~Trie图上的节点个数] = -1
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
;
* + ;
];
][][][];
struct Aho{
struct StateTable{
int Next[Letter];
int fail, cnt;
}Node[Max_Tot];
int Size;
queue<int> que;
inline void init(){
while(!que.empty()) que.pop();
memset(Node[].Next, , ].Next));
Node[].fail = Node[].cnt = ;
Size = ;
}
inline void insert(char *s){
;
; s[i]; i++){
int idx = mp[s[i]];
if(!Node[now].Next[idx]){
memset(Node[Size].Next, , sizeof(Node[Size].Next));
Node[Size].fail = Node[Size].cnt = ;
Node[now].Next[idx] = Size++;
}
now = Node[now].Next[idx];
}
Node[now].cnt++;
}
inline void BuildFail(){
Node[].fail = ;
; i<Letter; i++){
].Next[i]){
Node[Node[].Next[i]].fail = ;
que.push(Node[].Next[i]);
}].Next[i] = ;///必定指向根节点
}
while(!que.empty()){
int top = que.front(); que.pop();
Node[top].cnt += Node[Node[top].fail].cnt;
; i<Letter; i++){
int &v = Node[top].Next[i];
if(v){
que.push(v);
Node[v].fail = Node[Node[top].fail].Next[i];
}else v = Node[Node[top].fail].Next[i];
}
}
}
}ac;
];
***+][];
int Solve()
{
]; memset(num, , sizeof(num));
; S[i]; i++) num[mp[S[i]]]++;
;
; A<=num[]; A++)
; T<=num[]; T++)
; G<=num[]; G++)
; C<=num[]; C++)
Hash[A][T][G][C] = HashCnt++;
; j<=ac.Size; j++)
; i<=HashCnt; i++)
dp[i][j] = -;
dp[][] = ;
; A<=num[]; A++){
; T<=num[]; T++){
; G<=num[]; G++){
; C<=num[]; C++){
; i<ac.Size; i++){
int j = Hash[A][T][G][C];
){
; k<; k++){
&& A == num[]) continue;
&& T == num[]) continue;
&& G == num[]) continue;
&& C == num[]) continue;
int a, t, g, c;
a = (k==), t = (k==);
g = (k==), c = (k==);
dp[Hash[A+a][T+t][G+g][C+c]][ac.Node[i].Next[k]]
= max(dp[Hash[A+a][T+t][G+g][C+c]][ac.Node[i].Next[k]],
dp[j][i] + ac.Node[ac.Node[i].Next[k]].cnt);
}
}
}
}
}
}
}
;
]][num[]][num[]][num[]];
; i<ac.Size; i++)
ans = max(ans, dp[MaxNum][i]);
return ans;
}
int main(void)
{
;
mp[, mp[;
mp[, mp[;
while(~scanf("%d", &n) && n){
ac.init();
; i<n; i++){
scanf("%s", S);
ac.insert(S);
}ac.BuildFail();
scanf("%s", S);
printf("Case %d: %d\n", Case++, Solve());
}
;
}