我们对作文库建出广义后缀自动机。考虑用(SAM)处理出来一个数组(mx[i]),表示从作文的第(i)个位置向左最远在作文库中出现的子串的长度。这个东西可以在(SAM)上跑(trans)边来实现(其实求出来的是作文前i位在作文库中出现的最长后缀)。
处理出来这个东西,我们考虑用(DP)求答案。发现直接用(DP)求并不是很好求,所以要在外面套一个二分答案。(DP)还要用单调队列优化。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=1200000;
int ma[N],n,m,q[N],dp[N],L;
char s[N];
struct SAM{
int u,tot,len[N],trans[N][27],fa[N];
void init(){tot=u=1;}
void rebuild(){u=1;}
void ins(int c){
int x=++tot;len[x]=len[u]+1;
for(;u&&trans[u][c]==0;u=fa[u])trans[u][c]=x;
if(u==0)fa[x]=1;
else{
int v=trans[u][c];
if(len[u]+1==len[v])fa[x]=v;
else{
int w=++tot;
fa[w]=fa[v];
len[w]=len[u]+1;
memcpy(trans[w],trans[v],sizeof(trans[w]));
fa[x]=fa[v]=w;
for(;u&&trans[u][c]==v;u=fa[u])trans[u][c]=w;
}
}
u=x;
}
void pre_work(){
int now=1;
for(int i=1;i<=L;i++){
int c=s[i]-'0';
for(;now&&!trans[now][c];now=fa[now]);
if(!now){ma[i]=0,now=1;continue;}
ma[i]=min(ma[i-1]+1,len[now]+1);
now=trans[now][c];
}
}
}sam;
bool judge(int x){
int l=1,r=0;
for(int i=0;i<=L;i++)dp[i]=0;
for(int i=1;i<=L;i++){
while(l<=r&&q[l]<i-ma[i])l++;
if(l<=r)dp[i]=dp[q[l]]+i-q[l];
dp[i]=max(dp[i-1],dp[i]);
while(l<=r&&dp[i-x+1]-(i-x+1)>=dp[q[r]]-q[r])r--;
q[++r]=i-x+1;
}
return 10*dp[L]>=9*L;
}
int main(){
scanf("%d%d",&n,&m);
sam.init();
for(int i=1;i<=m;i++){
scanf("%s",s+1);
L=strlen(s+1);
for(int i=1;i<=L;i++)sam.ins(s[i]-'0');
sam.rebuild();
}
for(int i=1;i<=n;i++){
scanf("%s",s+1);
L=strlen(s+1);
sam.pre_work();
int l=1,r=L,ans;
while(l<=r){
int mid=(l+r)>>1;
if(judge(mid)){
ans=mid;
l=mid+1;
}
else r=mid-1;
}
printf("%d
",ans);
}
return 0;
}