首先这个题目显然是要二分转换成判断可行性的
之后我们考虑DP
设f(i)表示 1->i 熟悉的子串的长度的最大值
那么对于i这个点，要么不在熟悉的子串中，要么在熟悉的子串中
所以得到
f(i)=max(f(i-1),f(j)+i-j);
其中i-j是划分的熟悉的子串的长度，要满足以下条件：
1、i-j>=k (k为二分出来的值）
2、[j+1,i]这段串是给定标准文章库的一个子串
我们又知道若[j+1,i]是一个满足条件的子串，那么[j+2,i]也一定满足条件
假设我们已知最小的p满足[p+1,i]是一个满足条件的子串，定义L=i-p
那么条件2转化为 i-j<=L
求特定区间的最大值，且左右端点是单调的，我们是可以用单调队列的
那么现在问题就是求解最小的p使得[p+1,i]满足条件
即求解给定串S的一个前缀的最长满足条件的后缀，这时可以用后缀自动机做的
每次只需要在上次的基础上顺着parent树向上寻找匹配就可以了
注意：当寻找到SAM上的一个可匹配的节点时，当前的L并不一定是这个合法节点的len值+1
因为SAM上的节点的len值为其可以取得的长度的最大值，它有可能比上一次的L要大
所以我的代码对这种情况进行了一下处理QAQ
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<algorithm>
using namespace std; const int maxn=1100010;
int n,m,cnt,la,len;
char s[maxn];
struct Node{
int next[3];//0 1 2
int len,link;
}st[maxn<<1];
int Q[maxn],h,t;
int f[maxn]; void init(){
cnt=la=0;
st[0].link=-1;
}
void add(int c){
int cur=++cnt;
st[cur].len=st[la].len+1;
int p;
for(p=la;p!=-1&&st[p].next[c]==0;p=st[p].link)st[p].next[c]=cur;
if(p==-1)st[cur].link=0;
else{
int q=st[p].next[c];
if(st[q].len==st[p].len+1)st[cur].link=q;
else{
int clone=++cnt;
st[clone]=st[q];
st[clone].len=st[p].len+1;
for(;p!=-1&&st[p].next[c]==q;p=st[p].link)st[p].next[c]=clone;
st[q].link=st[cur].link=clone;
}
}la=cur;
}
bool check(int k){
h=1;t=0;f[0]=0;
int p=0,L=0;
for(int i=1;i<=len;++i){
if(i>=k){
while(h<=t&&f[Q[t]]-Q[t]<f[i-k]-(i-k))t--;
Q[++t]=i-k;
}
int now=s[i]-'0';
int cur=p;
for(;p!=-1&&st[p].next[now]==0;p=st[p].link);
f[i]=f[i-1];
if(p==-1){p=0;L=0;continue;}
if(p==cur)L++;
else L=st[p].len+1;
p=st[p].next[now];
while(h<=t&&i-Q[h]>L)h++;
if(h<=t)f[i]=max(f[i],f[Q[h]]-Q[h]+i);
}return len*9<=f[len]*10;
} int main(){
scanf("%d%d",&n,&m);init();
for(int i=1;i<=m;++i){
scanf("%s",s+1);len=strlen(s+1);
for(int j=1;j<=len;++j)add(s[j]-'0');
add(2);
}
while(n--){
scanf("%s",s+1);len=strlen(s+1);
int L=0,R=len;
while(L<R){
int mid=L+((R-L+1)>>1);
if(check(mid))L=mid;
else R=mid-1;
}printf("%d\n",L);
}return 0;
}