剪贴板 500zyjjp

```cpp #include <bits/stdc++.h> #define ll long long using namespace std; const int N = 2e6 + 10; const int C = 3; int _t, _q; int f[N], g[N]; int hd, tl, q[N]; int ct[N][C], ctr = 1; int le[N], lk[N]; int ch[N][C], tot = 1; int ps[N]; char s[N]; void ins_trie() { int n = strlen(s + 1), u = 1; for (int i = 1; i <= n; i++) { int c = s[i] - '0'; if (!ct[u][c]) ct[u][c] = ++ctr; u = ct[u][c]; } } int ins_sam(int la, int c) { int cur = ++tot; le[cur] = le[la] + 1; int p = la; while (p && !ch[p][c]) ch[p][c] = cur, p = lk[p]; if (!p) { lk[cur] = 1; return cur; } int q = ch[p][c]; if (le[q] == le[p] + 1) { lk[cur] = q; return cur; } int cp = ++tot; le[cp] = le[p] + 1, lk[cp] = lk[q]; for (int i = 0; i < 2; i++) ch[cp][i] = ch[q][i]; while (p && ch[p][c] == q) ch[p][c] = cp, p = lk[p]; lk[cur] = lk[q] = cp; return cur; } void bfs() { queue <int> q; q.push(1), ps[1] = 1; while (!q.empty()) { int u = q.front(); q.pop(); for (int i = 0; i < 2; i++) { if (!ct[u][i]) continue; ps[ct[u][i]] = ins_sam(ps[u], i); q.push(ct[u][i]); } } } bool check(int x, int n) { hd = tl = 1; for (int i = 1; i <= n; i++) q[i] = g[i] = 0; for (int i = x; i <= n; i++) { while (hd <= tl && q[hd] < i - f[i]) hd++; int j = q[hd]; if (i - f[i] <= j && j <= i - x) g[i] = max(g[i - 1], g[j] + i - j); else g[i] = g[i - 1]; while (hd <= tl && g[q[tl]] - q[tl] < g[i - x + 1] - i + x - 1) tl--; q[++tl] = i - x + 1; } int k = ceil(0.9 * n); return (g[n] >= k); } int main() { cin >> _q >> _t; for (int _ = 1; _ <= _t; _++) { cin >> s + 1; ins_trie(); } bfs(); for (int _ = 1; _ <= _q; _++) { cin >> s + 1; int n = strlen(s + 1), u = 1, te = 0; for (int i = 1; i <= n; i++) { int c = s[i] - '0'; while (u && !ch[u][c]) u = lk[u], te = le[u]; if (!u) { f[i] = te = 0, u = 1; continue; } u = ch[u][c], f[i] = ++te; } int l = 0, r = N - 1; while (l < r) { int M = (l + r + 1) >> 1; if (check(M, n)) l = M; else r = M - 1; } cout << l << "\n"; } return 0; } ```