记录编号	254645	评测结果	AAAAEEEEEE
题目名称	[HEOI 2016] 字符串	最终得分	40
用户昵称	神利·代目	是否通过	未通过
代码语言	C++	运行时间	1.073 s
提交时间	2016-04-25 15:33:22	内存使用	33.58 MiB

#include<stdio.h>
 void in(int &x){for(x=getchar();x<48||x>57;x=getchar());x^=48;for(int tmp=getchar();47<tmp&&tmp<58;tmp=getchar())x=(x<<1)+(x<<3)+(tmp^48);}
 int MIN(int A,int B){return A<B?A:B;}
int n,m,c[100010],t1[100010],t2[100010],sa[100010];
char s[100010];
void get_sa(int n,int m){
	int i,*x=t1,*y=t2,*z;
	for(i=0;i<n;++i)++c[x[i]=s[i]];
	for(i=1;i<m;++i)c[i]+=c[i-1];
	for(i=0;i<n;++i)sa[--c[x[i]]]=i;
	for(int k=1,p=0;p<n;k<<=1,m=p){
		for(i=n-k,p=0;i<n;++i)y[p++]=i;
		for(i=0;i<n;++i)if(sa[i]>=k)y[p++]=sa[i]-k;
		for(i=0;i<m;++i)c[i]=0;
		for(i=0;i<n;++i)++c[x[y[i]]];
		for(i=1;i<m;++i)c[i]+=c[i-1];
		for(i=n-1;~i;--i)sa[--c[x[y[i]]]]=y[i];
		z=x,x=y,y=z,x[sa[0]]=0,p=1;
		for(i=1;i<n;++i)
		    x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?p-1:p++;
	}
}
int rank[100010],lcp[100010];
void get_lcp(int n){
	int i,j,k=0;
	for(i=1;i<=n;++i)rank[sa[i]]=i;
	for(i=0;i<n;lcp[rank[i++]]=k)
		for(k?--k:k=0,j=sa[rank[i]-1];s[i+k]==s[j+k];++k);
}
int ci,st[100010][20];
void get_st(){
	for(ci=1;1<<ci<n;++ci);
	for(int i=1;i<=n;++i)st[i][0]=lcp[i];
	for(int i=1;i<=ci;++i)
		for(int j=1;j<=n;++j)
		    st[j][i]=MIN(st[j][i-1],st[j+(1<<i-1)][i-1]);
}
int cnt,rt[100010];
struct node{int l,r,s;}o[2000010];
 void build(int l,int r,int t,int tt,int x){
	o[t].s=o[o[tt].l].s+o[o[tt].r].s+1;
	if(l==r)return;
	int mid=l+r>>1;
	if(x<=mid)o[t].l=++cnt,o[t].r=o[tt].r,build(l,mid,o[t].l,o[tt].l,x);
	else o[t].r=++cnt,o[t].l=o[tt].l,build(mid+1,r,o[t].r,o[tt].r,x);
}
 int sum(int l,int r,int t,int L,int R){
	if(L<=l&&r<=R)return o[t].s;
	int mid=l+r>>1;
	if(R<=mid)return sum(l,mid,o[t].l,L,R);
	if(L>mid)return sum(mid+1,r,o[t].r,L,R);
	return sum(l,mid,o[t].l,L,R)+sum(mid+1,r,o[t].r,L,R);
}
 bool judge(int a,int b,int x,int len){
	int l=rank[x],r=rank[x];
	for(int i=ci;~i;--i){
		if(r+(1<<i)<=n&&st[r+1][i]>=len)
		    r+=1<<i;
		if(l>=1<<i&&st[l-(1<<i)+1][i]>=len)
		    l-=1<<i;
	}
	int num=sum(0,n-1,rt[r],a,b);
	if(l)num-=sum(0,n-1,rt[l-1],a,b);
	return num?1:0;
}
int main(){
	freopen("heoi2016_str.in","r",stdin);
	freopen("heoi2016_str.out","w",stdout);
	in(n),in(m),scanf("%s",s);
	get_sa(n+1,128),get_lcp(n);
	get_st();
	for(int i=1;i<=n;++i)
		build(0,n-1,rt[i]=++cnt,rt[i-1],sa[i]);
	for(int i=1,a,b,c,d,l,r,mid,ans;i<=m;++i){
		in(a),in(b),in(c),in(d),--a,--b,--c,--d;
		for(l=0,r=MIN(b-a+1,d-c+1);l<=r;){
			mid=l+r>>1;
			if(judge(a,b-mid+1,c,mid))ans=mid,l=mid+1;
			else r=mid-1;
		}
		printf("%d\n",ans);
	}
}