[cmdoi2019]口头禅

被卡空间的代码：

#include<bits/stdc++.h>
#define N 810010
using namespace std;
struct no{
	int l,r,id;
}a[100010];
int operator <(no x,no y){
	return x.l<y.l||(x.l==y.l&&x.r<y.r);
}
int operator ==(no x,no y){
	return (x.l==y.l)&&(x.r==y.r);
}
int fa[N],t[N][2],len[N],la,ct,n,m,le[N],cc,st[20010],*g[20010],rt[20010],ans[100010],h[400010];
char *s[20010],v[100010];
struct sam{
	int add(int c,int id){
		int cur=++ct,p=la;
		len[cur]=len[la]+1;
		la=cur;
		for(;p&&!t[p][c];p=fa[p])
			t[p][c]=cur;
		if(!p)
			fa[cur]=rt[id];
		else{
			int q=t[p][c];
			if(len[p]+1==len[q])
				fa[cur]=q;
			else{
				int cl=++ct;
				len[cl]=len[p]+1;
				memcpy(t[cl],t[q],sizeof(t[cl]));
				fa[cl]=fa[q];
				fa[cur]=fa[q]=cl;
				for(;t[p][c]==q;p=fa[p])
					t[p][c]=cl;
			}
		}
		return cur;
	}
	void bd(char *s,int id){
		rt[id]=++ct;
		la=ct;
		for(int i=1;s[i];i++)
			add(s[i]-‘0‘,id);
	}
}sg[N];
void gt(int l,int r,int v,vector<no>q){
	vector<no>q1,q2;
	if(l>r)return;
	int tp=0;
	while(1){
		for(int i=l;i<=r;i++)
			if(le[i]<=v)
				st[++tp]=i;
		if(tp)
			break;
		v*=2; 
	}
	int md=st[(tp+1)/2],*pt=h;
	for(int i=l;i<=r;i++){
		g[i]=pt;
		pt+=le[md]+1;
	}
	for(int i=1;i<=le[md];i++)
		g[md][i]=i;
	for(int i=md-1;i>=l;i--){
		int p=rt[i],ll=0;
		for(int j=1;j<=le[md];j++){
			int ch=s[md][j]-‘0‘;
			while(p&&!t[p][ch]){
				p=fa[p];
				ll=len[p];
			}
			if(!p)
				p=rt[i];
			else{
				p=t[p][ch];
				ll++;
			}
			g[i][j]=min(g[i+1][j],ll);
		}
	}
	for(int i=md+1;i<=r;i++){
		int p=rt[i],ll=0;
		for(int j=1;j<=le[md];j++){
			int ch=s[md][j]-‘0‘;
			while(p&&!t[p][ch]){
				p=fa[p];
				ll=len[p];
			}
			if(!p)
				p=rt[i];
			else{
				p=t[p][ch];
				ll++;
			}
			g[i][j]=min(g[i-1][j],ll);
		}
	}
	for(int i=0;i<q.size();i++){
		no x=q[i];
		int c=x.l,d=x.r;
		if(d<md)
			q1.push_back(x);
		else if(c>md)
			q2.push_back(x);
		else{
			if(i&&x==q[i-1])
				ans[x.id]=ans[q[i-1].id];
			else{
				int va=0;
				for(int j=1;j<=le[md];j++)
					va=max(va,min(g[c][j],g[d][j]));
				ans[x.id]=va;
			}
		}
	}
	q.clear();
	gt(l,md-1,v,q1);
	gt(md+1,r,v,q2);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%s",v+1);
		le[i]=strlen(v+1);
		s[i]=new char[le[i]+2];
		for(int j=1;j<=le[i];j++)
			s[i][j]=v[j];
		s[i][le[i]+1]=0;
		sg[i].bd(s[i],i);
	}
	cc=1;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&a[i].l,&a[i].r);
		a[i].id=i;
	}
	sort(a+1,a+m+1);
	vector<no>q;
	for(int i=1;i<=m;i++)
		q.push_back(a[i]);
	gt(1,n,1,q);
	for(int i=1;i<=m;i++)
		printf("%lld\n",ans[i]);
}

[cmdoi2019]口头禅

原文：https://www.cnblogs.com/ctmlpfs/p/13800779.html