题解

#include<bits/stdc++.h>
#define neko 2000010
#define chkmax(a,b) ((a)>(b)?(a):(b))
#define f(i,a,b) for(register int i=(a);i<=(b);i=-(~(i)))
typedef int arr[neko];
arr link,len,dp,maxlen,q;
int n,m,nex[neko][3];
namespace SAM
{
int slen,cnt,cur,last;
void find(char *s)
{
int p=0,now=0,x;
slen=strlen(s+1);
f(i,1,slen)
{
x=s[i]-'0';
if(nex[p][x])++now,p=nex[p][x];
else
{
for(;p!=-1&&(!nex[p][x]);p=link[p]);
if(p==-1)p=0,now=0;
else now=len[p]+1,p=nex[p][x];
}maxlen[i]=now;
}
}//this is right
void extend(char *s)
{
int p,q,clone,x;
link[0]=-1,slen=strlen(s+1);s[++slen]='2';
f(i,1,slen)
{
cur=++cnt,len[cur]=len[last]+1;
x=s[i]-'0';
for(p=last;p!=-1&&(!nex[p][x]);p=link[p])nex[p][x]=cur;
if(p==-1)link[cur]=0;
else
{
q=nex[p][x];
if(len[p]+1==len[q])link[cur]=q;
else
{
clone=++cnt;
len[clone]=len[p]+1;
link[clone]=link[q];
f(j,0,1)nex[clone][j]=nex[q][j];
for(;p!=-1&&(nex[p][x]==q);p=link[p])nex[p][x]=clone;
link[q]=link[cur]=clone;
}
}last=cur;
}
}
}
bool check(int l)
{
int slen=SAM::slen,j,H=0,T=-1;
//easily(?) to prove that it has a monotonicity of decision making
f(i,0,l-1)dp[i]=0;
f(i,l,slen)
{
dp[i]=dp[i-1];
while(H<=T&&(dp[i-l]-(i-l))>(dp[q[T]]-q[T]))--T;
q[++T]=i-l;
while(H<=T&&q[H]<(i-maxlen[i]))++H;
if(H<=T)dp[i]=chkmax(dp[i],dp[q[H]]-q[H]+i);//i-(j+1)+1
//f(j,i-maxlen[i],i-l)if(dp[j]+(i-j)>dp[i])dp[i]=dp[j]+(i-j);//i-(maxlen[i]+1)+1
}//f(i,1,slen)printf("%d ",dp[i]);puts("");
return dp[slen]10>=slen9;
}
char s[neko];
#define mid ((l+r)>>1)
int main()
{
using namespace SAM;
int l,r;
scanf("%d%d",&n,&m);
f(i,1,m)scanf("%s",s+1),extend(s);
f(i,1,n)
{
scanf("%s",s+1);
l=1,r=strlen(s+1);
find(s);
while(l<=r)
{
//printf("%d %d %d\n",l,r,mid);
if(check(mid))l=mid+1;
else r=mid-1;
}printf("%d\n",mid);
}
return 0;
}