【BZOJ2806】【CTSC2012】Cheat 广义后缀自动机+二分+Dp

## 题目 [题目在这里](https://www.lydsy.com/JudgeOnline/problem.php?id=2806) ## 思路&做法 我们先对标准作文库建广义后缀自动机。 然后对于每一篇阿米巴的作文， 我们首先把放到广义后缀自动机跑一遍， 对于每一个位置， 记录公共子串的长度$($即代码和下文中的$val$数组$)$ 接着我们二分答案， 用DP检验。 Dp方程很好想， $ d_i = max \{ d_j + i - j \ | \ i-val_i <= j <= i-lim \} $ 可以用单点队列优化。 ## 代码 ```cpp #include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> using namespace std; const int N = 1300010; //数组不能太大， 会T的 int n, m; int val[N]; struct Suffix_Automaton { int nxt[N][2], fail[N], sz; int len[N]; int root; Suffix_Automaton() { } inline int newnode(int l) { memset(nxt[sz], 0, sizeof(nxt[sz])); fail[sz] = 0; len[sz] = l; return sz++; } void init() { sz = 1; root = newnode(0); } inline int idx(char x) { return x - '0'; } int add(int last, char x) { int c = idx(x); if (nxt[last][c]) { int p = last, q = nxt[last][c]; if (len[q] == len[p] + 1) return q; else { int u = newnode(len[p] + 1); for (int i = 0; i < 2; i++) nxt[u][i] = nxt[q][i]; fail[u] = fail[q]; fail[q] = u; while (p && nxt[p][c] == q) { nxt[p][c] = u; p = fail[p]; } return u; } } else { int now = newnode(len[last] + 1); int p = last; while (p && !nxt[p][c]) { nxt[p][c] = now; p = fail[p]; } if (!p) fail[now] = root; else { int q = nxt[p][c]; if (len[q] == len[p] + 1) fail[now] = q; else { int u = newnode(len[p] + 1); for (int i = 0; i < 2; i++) nxt[u][i] = nxt[q][i]; fail[u] = fail[q]; fail[now] = fail[q] = u; while (p && nxt[p][c] == q) { nxt[p][c] = u; p = fail[p]; } } } return now; } } void insert(char *s) { int Len = strlen(s); int last = root; for (int i = 0; i < Len; i++) last = add(last, s[i]); } void work(char *str) { int cnt = 0; int now = root; int Len = strlen(str+1); for (int i = 1; i <= Len; i++) { int c = idx(str[i]); if (nxt[now][c]) { cnt++; now = nxt[now][c]; } else { while (now && !nxt[now][c]) now = fail[now]; if (!now) { now = root; cnt = 0; } else { cnt = len[now] + 1; now = nxt[now][c]; } } val[i] = cnt; } } } tzw; int d[N]; int Q[N], hd, tl; bool check(char *s, int lim) { int Len = strlen(s+1); for (int i = 0; i <= lim; i++) d[i] = 0; hd = 0, tl = 1; for (register int i = lim; i <= Len; i++) { d[i] = d[i-1]; if (i > lim) //这里一定不能去掉， 去掉会RE { while (hd < tl && Q[hd] < i-val[i]) hd++; while (hd < tl && d[Q[tl-1]]+i-Q[tl-1] < d[i-lim]+i-(i-lim)) tl--; Q[tl++] = i - lim; } if (val[i] >= lim) d[i] = max(d[i], d[Q[hd]] + i - Q[hd]); } return 10*d[Len] >= 9*Len; } int solve(char *s) { int l = 1, r = strlen(s+1); while (l <= r) { int mid = (l+r) >> 1; if (check(s, mid)) l = mid + 1; else r = mid - 1; } return r; } char str[N]; int main() { scanf("%d %d", &n, &m); tzw.init(); for (register int i = 1; i <= m; i++) { scanf("%s", str); tzw.insert(str); } for (register int i = 1; i <= n; i++) { scanf("%s", str+1); tzw.work(str); if(!check(str, 1)) puts("0"); else printf("%d\n", solve(str)); } return 0; } ``` ## 备注 注释里的坑我全踩了