代码在这里
```cpp
#include <bits/stdc++.h>
int m, mlen, n;
char S[1100005];
const int N = 1.1e6 + 5;
int ch[N][2], ctot = 1, tr[N * 2][2], tot, last[N * 2], link[N * 2], len[N * 2];
void insert(char s[], int n){
int now = 1;
for(int i = 1; i <= n; ++i){
if(!ch[now][s[i] - '0']) ch[now][s[i] - '0'] = ++ctot;
now = ch[now][s[i] - '0'];
}
return ;
}
int insert(int lst, int x){
int p = lst, cur = ++tot;
len[cur] = len[p] + 1;
while(p != -1 && !tr[p][x]){
tr[p][x] = cur;
p = link[p];
}
if(p == -1) link[cur] = 0;
else {
int q = tr[p][x];
if(len[p] + 1 == len[q]) link[cur] = q;
else {
int clone = ++tot;
link[clone] = link[q];
memcpy(tr[clone], tr[q], sizeof tr[clone]);
len[clone] = len[p] + 1;
link[q] = clone;
link[cur] = clone;
while(p != -1 && tr[p][x] == q){
tr[p][x] = clone;
p = link[p];
}
}
}
return cur;
}
void bfs(){
std::queue <int> q; len[0] = 0, link[0] = -1; q.push(1);
while(q.size()){
int u = q.front(); q.pop();
for(int i = 0; i <= 1; ++i) if(ch[u][i]) last[ch[u][i]] = insert(last[u], i), q.push(ch[u][i]);
}
return ;
}
int f[1100005], Q[1100005], L, R;
int check(int k){
if(k == 0) return 1;
f[0] = 0; int now = 0;
L = 1, R = 0;
for(int i = 1; i <= n; ++i){
int x = S[i] - '0'; f[i] = 0;
while(now != 0 && !tr[now][x]) now = link[now];
if(!tr[now][x]) {
f[i] = f[i - 1];
L = 1, R = 0;
continue;
}
now = tr[now][x];
/* if(len[now] < k) {
f[i] = f[i - 1];
L = 1, R = 0;
continue;
}
while(L <= R && Q[L] < i - len[now]) ++L;
if(i >= k){
while(L <= R && f[Q[R]] - Q[R] <= f[i - k] - (i - k)) --R;
Q[++R] = i - k;
}
if(L > R) f[i] = f[i - 1];
else f[i] = i + f[Q[L]] - Q[L];*/
f[i] = f[i - 1];
for(int j = i - len[now]; j <= i - k; ++j) f[i] = std::max(f[i], f[j] + i - j);
}
return f[n] * 10 >= n * 9;
}
void solve(){
scanf("%s", S + 1); n = strlen(S + 1);
int l = 0, r = mlen, mid;
while(l < r){
mid = l + r + 1 >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
printf("%d\n", l);
return ;
}
int main(){
int T; scanf("%d%d", &T, &m);
for(int i = 1; i <= m; ++i){
scanf("%s", S + 1); int le = strlen(S + 1);
insert(S, le); mlen = std::max(mlen, le);
}
bfs();
while(T--) solve();
return 0;
}
```
by 蒟蒻君HJT @ 2023-11-14 13:15:58
注释掉的是单调队列优化，注释后面的两行是暴力枚举可行点转移
by 蒟蒻君HJT @ 2023-11-14 13:16:37
管理楼下
by xtlzq @ 2023-11-14 13:42:13
现在 65 了，WA 0 的原因是学艺不精，SAM 跑匹配的时候匹配长度并不是节点的 $maxlen$，而是需要维护的一个东西
by 蒟蒻君HJT @ 2023-11-14 13:44:02
y
by GoodLuckCat @ 2023-11-14 13:54:39
过了，还有一个问题是转移 $f_i$ 时没对 $f_{i-1}$ 取 $\max$
by 蒟蒻君HJT @ 2023-11-14 16:21:03
@[蒟蒻君HJT](/user/131591) 感谢前人，同样的问题。/bx
by Le0Chan @ 2023-12-02 09:44:05