求卡常

#include <bits/stdc++.h>
using namespace std;
#define ls k<<1
#define rs k<<1|1

const int N=2e6+5;

int n,m,s[N],x[N],y[N],c[N],sa[N],rk[N],id[N],l[N],r[N],height[N],mn[N*4],mn2[N*4],col[N],llst[N],rlst[N],cnt,f[N],len[N];

void SA(){
	n=cnt;
	m=N-1;
	memcpy(s,x,sizeof s);
	for(int i=1;i<=n;++i)c[x[i]]++;
	for(int i=1;i<=m;++i)c[i]+=c[i-1];
	for(int i=n;i;--i)sa[c[x[i]]--]=i;
	for(int k=1;k<=n;k<<=1){
		int num=0;
		for(int i=n-k+1;i<=n;++i)y[++num]=i;
		for(int i=1;i<=n;++i)
			if(sa[i]>k)y[++num]=sa[i]-k;
		memset(c,0,sizeof c);
		for(int i=1;i<=n;++i)c[x[i]]++;
		for(int i=1;i<=m;++i)c[i]+=c[i-1];
		for(int i=n;i;--i)sa[c[x[y[i]]]--]=y[i];
		swap(x,y);
		num=0;
		for(int i=1;i<=n;++i)
			if(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])x[sa[i]]=num;
			else x[sa[i]]=++num;
		if(num==n)break;
		m=num;
	}
	//for(int i=1;i<=n;++i)cout<<sa[i]<<" ";
	//cout<<"\n";
}

void build(int k,int l,int r){
	if(l==r){
		mn[k]=height[l];
		return;
	}
	int mid=(l+r)>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	mn[k]=min(mn[ls],mn[rs]);
}

int query(int k,int l,int r,int a,int b){
	if(a>b)return 0;
	if(a<=l&&r<=b)return mn[k];
	int mid=(l+r)>>1,res=2e9;
	if(a<=mid)res=min(res,query(ls,l,mid,a,b));
	if(b>mid)res=min(res,query(rs,mid+1,r,a,b));
	return res;
}

void getheight(){
	for(int i=1;i<=n;++i)rk[sa[i]]=i;
	int k=0;
	for(int i=1;i<=n;++i){
		if(rk[i]==1)continue;
		if(k)--k;
		int j=sa[rk[i]-1];
		while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])++k;
		height[rk[i]]=k;
	}
	build(1,1,n);
	for(int i=1,lst=1;i<=n;++i){
		int cnt=(sa[i]<l[1]);
		if(!cnt)llst[i]=lst;
		else lst=i;
	}
	for(int i=n,lst=n;i>=1;--i){
		int cnt=(sa[i]<l[1]);
		if(!cnt)rlst[i]=lst;
		else lst=i;
	}
}

int tag[N*4],tag2[N*4];

inline void addtag(int k,int c){
	tag[k]=min(tag[k],c);
	mn2[k]=min(mn2[k],c);
}

inline void addtag2(int k,int c){
	tag2[k]=c;
	mn2[k]=c;
}

inline void pushdown(int k,int l,int r){
	if(tag2[k]!=-1){
		addtag2(ls,tag2[k]);
		addtag2(rs,tag2[k]);
		tag2[k]=-1;
	}
	if(tag[k]==0x3f3f3f3f)return;
	addtag(ls,tag[k]);
	addtag(rs,tag[k]);
	tag[k]=0x3f3f3f3f;
}

int tmp;

inline void update2(int k,int l,int r,int a,int b,int c){
	if(a>b)return;
	if(a<=l&&r<=b){
		addtag(k,c);
		if(a==b)tmp=mn2[k];
		return;
	}
	pushdown(k,l,r);
	int mid=(l+r)>>1;
	if(a<=mid)update2(ls,l,mid,a,b,c);
	if(b>mid)update2(rs,mid+1,r,a,b,c);
	mn2[k]=min(mn2[ls],mn2[rs]);
}

inline void update3(int k,int l,int r,int a,int b,int c){
	if(a>b)return;
	if(a<=l&&r<=b){
		addtag2(k,c);
		return;
	}
	pushdown(k,l,r);
	int mid=(l+r)>>1;
	if(a<=mid)update3(ls,l,mid,a,b,c);
	if(b>mid)update3(rs,mid+1,r,a,b,c);
	mn2[k]=min(mn2[ls],mn2[rs]);
}

inline int query2(int k,int l,int r,int a){
	if(l==r)return mn2[k];
	pushdown(k,l,r);
	int mid=(l+r)>>1;
	if(a<=mid)return query2(ls,l,mid,a);
	else return query2(rs,mid+1,r,a);
}

bool check(int x,int y){
	update3(1,1,n-l[1]+1,l[y]-l[1]+1,r[y]-l[1]+1,1e9);
	int lst=0;
	for(int i=l[y];i<=r[y];++i){
		if(len[i]>=x){
			int v=min(i+len[i]-1,r[y]);
			update2(1,1,n-l[1]+1,min(i-1+x,r[y])-l[1]+1,v-l[1]+1,lst);
		}
		update2(1,1,n-l[1]+1,i-l[1]+1,i-l[1]+1,lst+1);
		lst=tmp;
	}
	return query2(1,1,n-l[1]+1,r[y]-l[1]+1)*10<=r[y]-l[y]+1;
}

int main(){
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
	memset(tag2,-1,sizeof tag2);
	memset(tag,0x3f,sizeof tag);
	int n;
	cin>>n>>m;
	for(int i=1;i<=m;++i){
		string t;
		cin>>t;
		for(int j=0;j<t.size();++j){
			x[++cnt]=t[j]-'0'+1;
			id[cnt]=i+n;
		}
		x[++cnt]=i+2;
	}
	for(int i=1;i<=n;++i){
		string t;
		cin>>t;
		l[i]=cnt+1;
		for(int j=0;j<t.size();++j){
			x[++cnt]=t[j]-'0'+1;
			id[cnt]=i;
		}
		r[i]=cnt;
		x[++cnt]=i+m+2;
		id[cnt]=i;
	}
	SA();
	getheight();
	for(int i=1;i<=n;++i){
		int L=0,R=r[i]-l[i]+100;
		for(int j=l[i];j<=r[i];++j){
			int u=rk[j];
			int kk=max(query(1,1,cnt,llst[u]+1,u),query(1,1,cnt,u+1,rlst[u]));
			len[j]=kk;
		}
		while(R-L>1){
			int mid=(L+R)/2;
			if(check(mid,i))L=mid;
			else R=mid;
		}
		cout<<L<<"\n";
	}
}