我们的目的就是找到一个最大的L0，使得该串的90%可以被分成若干长度>L0的字典串中的子串。
明显可以二分答案，对于二分的每个mid
我们考虑dp：f[i]表示前i个字符，最多能匹配上多少个字符。
发现转移端点是个不断前进的区间，单调队列优化就可以了。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#define N 2222222
#define eps 1e-8
using namespace std;
int last,tot,ch[N][],par[N],mx[N];
void add(int c){
int p=last,np=++tot;mx[np]=mx[p]+;
for(;p&&!ch[p][c];p=par[p])ch[p][c]=np;
if(!p)par[np]=;
else{
int q=ch[p][c];
if(mx[q]==mx[p]+)par[np]=q;
else{
int nq=++tot;
mx[nq]=mx[p]+;
par[nq]=par[q];
memcpy(ch[nq],ch[q],sizeof ch[nq]);
par[q]=par[np]=nq;
for(;p&&ch[p][c]==q;p=par[p])ch[p][c]=nq;
}
}last=np;
}
char s[N];
int n,m,len;
int pp[N],f[N];
void dfs(int v,int x,int l){
int t=s[x+]-'';pp[x]=l;
if(x==len)return ;
if(ch[v][t])dfs(ch[v][t],x+,l+);
else{
while(!ch[v][t])v=par[v],l=min(l,mx[v]);
dfs(ch[v][t],x+,l+);
}
}
int head,tail,q[N];
bool check(int x){
head=;tail=;
for(int i=;i<=len;i++){
f[i]=f[i-];
while(head<=tail&&q[head]<i-pp[i])head++;
if(head<=tail)f[i]=max(f[i],f[q[head]]+(i-q[head]));
if(i+-x>=){
int t=i+-x;
while(head<=tail&&f[t]-t>=f[q[tail]]-q[tail])tail--;
q[++tail]=t;
}
}
double ans=f[len],tot=len;
return ans>=(tot*0.9-eps);
}
int main(){
mx[]=-;
for(int i=;i<;i++)ch[][i]=;
last=++tot;
scanf("%d%d",&n,&m);
while(m--){
scanf("%s",s);len=strlen(s);
last=;for(int j=;j<len;j++)add(s[j]-'');
}
while(n--){
scanf("%s",s+);
len=strlen(s+);
dfs(,,);
int l=,r=len,mid,ans=;
while(l<=r){
mid=(l+r)>>;
if(check(mid)){ans=mid;l=mid+;}
else r=mid-;
}
printf("%d\n",ans);
}
return ;
}