题目链接
Vjudge Softmatch Topcoder 14531 Softmatch
题目大意
有一个长为 (n) 的主串 (S) 和 (K) 个长度 (leq n) 的模式串 ({p_i})，(S) 由 a 和 b 组成， (p_i) 由 1,2,3,4 组成，给定 (S) 串后我们可以选择其中一些字符改为大写，即 a->A 或 b->B，有如下的匹配规则：
a 匹配 0 和 1，A 匹配 2 和 3 。
b 匹配 0 和 2，B 匹配 1 和 3 。
设 (T) 在 (S) 中的匹配次数为 (f(T))，求 (max{sum_{i=1}^K f(p_i)})。
(1leq nleq 50), (1leq Kleq 5)
思路
(O(n^4K^2)) 做法
考虑 (dp)，注意到 (S) 每一位的两种选择互为补集，如果我们已经确定了一个串在位置 (i) 处匹配了 (k) 位，那么便可以直接还原出 (S) 在那 (k) 位的大小写选择情况，由于如果要 (dp) 转移，我们是必须要知道 (S) 这附近几位是什么样子的，于是设计这样的 (dp) 状态：
设 (dp_{i,j,k}) 为当前考虑到了 (S) 的第 (i) 位，和 (S) 匹配长度最大的串是 (p_j)，它的匹配长度是 (k) ，此时完成的匹配数量最大值。由于匹配长度最大，这 (k) 位已经包含了我们所有需要知道的信息，在到达这一状态时，把 (S) 的这 (k) 位还原出来，随后枚举下一位是选小写还是大写，把两种情况下的 (k+1) 位主串的后缀和 (K) 个模式串的前缀进行匹配，得到各自的最大匹配长度，然后就可以知道该决策下第 (i+1) 位完成了多少次匹配了。
状态数 (O(n^2K))，暴力转移一次是 (O(n^2K)) 的，所以时间复杂度为 (O(n^4K^2)) 。
(O(n^3K^2)) 做法
注意到上面每次的转移有重复可以利用的地方，有 (O(nK)) 个长度至多为 (n) 的确定的 (S) 片段，把他们预处理出来，再和 (K) 个串前后缀匹配，预处理 (O(n^3K^2))，(dp) 的时间复杂度降到了 (O(n^2K^2)) 。
(O(n^3K)) 做法
可以发现上面的做法还是有一点暴力的成分在里面的，复杂度瓶颈在于前后缀匹配这里。
不要考虑匹配长度这件事了，我们直接快进到匹配完成这件事，毕竟最终答案也只要完成匹配的数量，而匹配的最大数量也就 (nK) 个，背后最多对应着 (O(nK)) 中 (S) 不同选择方式的片段。设 (0) 为 (S) 这一位选择小写，(1) 为这一位选择大写，这样总共会有 (nK) 个 01串，将它们插入 (AC) 自动机里，重新来 (dp) 。
设 (dp_{i,j}) 为考虑到了 (S) 的第 (i) 位，目前位于 (AC) 自动机的节点 (j) 时的最大匹配数。先预处理出每个模式串在不同位置完成匹配对应 (AC) 自动机上的节点，设为 (match_{i,j})，另设 (cnt_i) 为第 (j) 个节点当前对应了多少个完成的匹配，(cnt) 很好计算，先在每个模式串直接匹配（即 (match_{i,j})）的节点记上一个 (1)，然后由浅到深扫一遍 (AC) 自动机，每个节点再从其 (fail) 节点处转移一次即可。
于是就可以直接 (dp) 转移了！枚举下一位是 (0) 还是 (1)，然后往下一个节点直接转移即可，设枚举的这一位是 (p)，即
(AC) 自动机共 (O(n^2K)) 个节点，(dp) 状态数 (O(n^3K))，转移 (O(1))，(cnt) 计算复杂度 (O(n^3K))，从而总时间复杂度 (O(n^3K)) 。在 (1leq N,Kleq 100) 的数据上虽然理论计算量上限 (1e8)，但实际上贴不到上限，(code) 实际表现极限数据 (421;ms) 。
Code
题目原意可能是想要大家找到一种多项式时间复杂度的做法即可，但是深挖下去，其实优化的空间还挺多的！借助这个特性，我把它出成了模拟赛的题，设了很多档部分分，然而结果没有人在这题上获得 (>0) 的分数。。
#include<iostream>
#include<vector>
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define per(i,b,a) for(int i = (b); i >= (a); i--)
#define N 55
#define K 6
#define Inf 0x3f3f3f3f
using namespace std;
struct Aho_Corasick_Automaton{
struct node{
int cnt, id;
node *son[2], *fail;
node(){
son[0] = son[1] = fail = 0;
cnt = id = 0;
}
} *root = new node, *q[N*N*K], *match[K][N];
int cnt, automaton[N*N*K][2];
node* insert(vector<int> choice){
node *x = root;
for(int k : choice){
if(x->son[k] == 0) x->son[k] = new node;
x = x->son[k];
}
return x;
}
void build(){
q[1] = root, root->id = 1, cnt = 1;
rep(i,0,1) if(root->son[i])
root->son[i]->fail = root, q[++cnt] = root->son[i], q[cnt]->id = cnt;
rep(i,2,cnt) rep(j,0,1) if(q[i]->son[j]){
q[++cnt] = q[i]->son[j];
node *nxt = q[i]->fail;
while(nxt != root && nxt->son[j] == 0) nxt = nxt->fail;
if(nxt->son[j]) nxt = nxt->son[j];
q[cnt]->id = cnt, q[cnt]->fail = nxt;
}
rep(i,1,cnt) rep(j,0,1){
if(q[i]->son[j]) automaton[i][j] = q[i]->son[j]->id;
else{
if(i == 1) automaton[1][j] = 1;
else automaton[i][j] = automaton[q[i]->fail->id][j];
}
}
}
void clear(){ rep(i,1,cnt) q[i]->cnt = 0; }
void prepare(){ rep(i,2,cnt) q[i]->cnt += q[i]->fail->cnt; }
} AC;
class Softmatch{
public:
int n, m, dp[N*N*K], pre[N*N*K];
int make_choice(char a, char b){
if(a == 'a') return b >= '2';
else return b == '1' || b == '3';
}
bool Max(int &a, int b){ return a < b ? a = b, 1 : 0; }
int count(string S, vector<string> patterns){
n = S.size(), m = patterns.size();
S = " "+S;
rep(i,0,m-1){
int len = patterns[i].size();
rep(j,1,n-len+1){
vector<int> choice;
rep(k,0,len-1) choice.push_back(make_choice(S[j+k], patterns[i][k]));
AC.match[i][j+len-1] = AC.insert(choice);
}
}
AC.build();
rep(i,1,AC.cnt) dp[i] = -Inf;
dp[1] = 0;
rep(i,1,n){
AC.clear();
rep(j,0,m-1) if(AC.match[j][i]) AC.match[j][i]->cnt++;
AC.prepare();
rep(j,1,AC.cnt) pre[j] = dp[j], dp[j] = -Inf;
rep(j,1,AC.cnt) if(pre[j] >= 0){
rep(k,0,1){
int nxt = AC.automaton[j][k];
Max(dp[nxt], pre[j]+AC.q[nxt]->cnt);
}
}
}
int ans = 0;
rep(i,1,AC.cnt) Max(ans, dp[i]);
return ans;
}
} solve;
int main(){
string a, b;
vector<string> read;
int k;
cin>>a>>k;
rep(i,1,k) cin>>b, read.push_back(b);
cout<< solve.count(a, read) <<endl;
return 0;
}