先把所有作文庫連起來建立一個字尾自動機。 對于每一個詢問，把字元串拿到自動機上去跑比對，計算出每一個位置能比對的最大長度val[i];然後二分一個L值,用dp來檢驗,設dp[i]為前i個字元的最大比對數 就有dp[i] = max(dp[j]+i-j | i-val[i] <= j <= i-L)。
維護一個隊列存放i-L~i的元素 然後檢驗隊首元素是否滿足i-val[i] <= q.front()，假設目前元素不滿足 當i變為i+1時 val[i]至多增長1 是以仍不滿足條件 以後也都不會滿足 是以可以把它彈出隊列。
tips：此題周遊字元串數組時用普通的周遊會T，需要用指針來周遊數組
#include <cstdio>
#include <map>
#include <algorithm>
#include<cstring>
#include<queue>
using namespace std;
#define N 2300010
#define ll long long
int root,last,cnt=0,fa[N],mx[N],son[N][3];
ll ans=0;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void ins(int ch){
int p=last,np=++cnt;mx[np]=mx[p]+1,last=np;
while(p && !son[p][ch]) son[p][ch]=np,p=fa[p];
if(!p) fa[np]=1;
else{
int q=son[p][ch];
if(mx[q]==mx[p]+1) fa[np]=q;
else{
int nq=++cnt;mx[nq]=mx[p]+1;
memcpy(son[nq],son[q],sizeof(son[q]));
fa[nq]=fa[q];fa[q]=fa[np]=nq;
while(son[p][ch]==q) son[p][ch]=nq,p=fa[p];
}
}
}
char str[N];
int val[N],dp[N];
bool check(int l,int len)
{
dp[0]=0;
queue<int>q;
for(int i=1;i<=len;i++)
{
dp[i]=dp[i-1];
int p=i-l;
if(p>=0)
{
while(!q.empty()&&dp[p]-p>dp[q.front()]-q.front()) q.pop();
q.push(p);
}
while(!q.empty()&&i-val[i]>q.front()) q.pop();
if(!q.empty()) dp[i]=max(dp[i],dp[q.front()]+i-q.front());
}
return 10*dp[len]>=9*len;
}
void iins(char *s)
{
for(char *c=s;*c;c++) ins(*c-'0');
ins(2);
}
int main(){
int n,m;
last=root=++cnt;
n=read();
m=read();
while(m--)
{
scanf("%s",str);
iins(str);
/*for(int j=1;j<=strlen(str+1);j++)
ins(str[j]-'0');
ins(2);*/
}
for(int i=1;i<=n;i++)
{
scanf("%s",str+1);
int len1=strlen(str+1),p=1,sz=0;
for(int j=1;j<=len1;j++){
if(son[p][str[j]-'0']) sz++,p=son[p][str[j]-'0'];
else{
while(p&&!son[p][str[j]-'0']) p=fa[p];
if(!p) sz=0,p=root;
else sz=mx[p]+1,p=son[p][str[j]-'0'];
}
val[j]=sz;
//printf("%d\n",sz);
}
int ans=0,l=0,r=len1;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid,len1)) l=mid+1,ans=mid;
else r=mid-1;
}
printf("%d\n",ans);
}
return 0;
}