记录编号	254368	评测结果	AAAAAAAAAAA
题目名称	[HEOI 2016] 字符串	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	11.844 s
提交时间	2016-04-25 09:48:07	内存使用	54.55 MiB

#define maxn 100010ul
#define maxt 4000010ul

#include <math.h>
#include <stdio.h>
#include <algorithm>

typedef unsigned int uint;

const int inf=0x3fffffff;
const uint base=131;

uint mp[maxn],pw[maxn];
int n,q,tot,st[17][maxn],rank[maxn],sa[maxn],L[maxt],R[maxt],tree[maxt],root[maxn];
char str[maxn];

void read(int &x){
	x=0;int c=getchar();
	while(c<'0'||c>'9') c=getchar();
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	return;
}

uint hsp(int l,int r){
	return mp[r]-mp[l-1]*pw[r-l+1];
}

int lcp(int a,int b,int c,int d){
	if(!a) return 0;
	int ret=0,mid,l=1,r=std::min(d-c+1,b-a+1);
	while(l<=r){
		mid=(l+r)>>1;
		if(hsp(a,a+mid-1)==hsp(c,c+mid-1)) l=mid+1,ret=mid;
		else r=mid-1;
	}
	return ret;
}

bool cmp(int a,int b){
	int ret=lcp(a,n,b,n),len=std::min(n-a+1,n-b+1);
	return ret==len?n-a<n-b:str[a+ret]<str[b+ret];
}

void build(int ls,int &rt,int l,int r,int pos){
	rt=++tot,L[rt]=L[ls],R[rt]=R[ls];
	tree[rt]=tree[ls]+1;
	if(l==r) return;
	int mid=(l+r)>>1;
	if(pos<=mid) build(L[ls],L[rt],l,mid,pos);
	else build(R[ls],R[rt],mid+1,r,pos);
	return;
}

void prepare(){
	pw[0]=1;for(int i=1;i<=n;i++) pw[i]=pw[i-1]*base;
	for(int i=1;i<=n;i++) mp[i]=mp[i-1]*base+str[i];
	for(int i=1;i<=n;i++) sa[i]=i;
	std::sort(sa+1,sa+n+1,cmp);
	for(int i=1;i<=n;i++) rank[sa[i]]=i;
	for(int i=1;i<=n;i++) build(root[i-1],root[i],1,n,rank[i]);
	for(int i=1;i<=n;i++) st[0][i]=lcp(sa[i-1],n,sa[i],n);
	for(int i=1;i<17;i++) for(int j=1<<i;j<=n;j++)
	    st[i][j]=std::min(st[i-1][j],st[i-1][j-(1<<(i-1))]);
	return;
}

int query(int ls,int rt,int l,int r,int posl,int posr){
	if(posl<=l&&posr>=r) return tree[rt]-tree[ls];
	int ret=0,mid=(l+r)>>1;
	if(posl<=mid) ret+=query(L[ls],L[rt],l,mid,posl,posr);
	if(posr>mid) ret+=query(R[ls],R[rt],mid+1,r,posl,posr);
	return ret;
}

bool check(int len,int a,int b,int c,int d){
	int s=rank[c],e=rank[c];
	for(int i=16;i>=0;i--) if(s>(1<<i)&&st[i][s]>=len) s-=1<<i;
	for(int i=16;i>=0;i--) if(e+(1<<i)<=n&&st[i][e+(1<<i)]>=len) e+=1<<i;
	return query(root[a-1],root[b-len+1],1,n,s,e)>0;
}

int main(){
	freopen("heoi2016_str.in","r",stdin);
	freopen("heoi2016_str.out","w",stdout);
	read(n),read(q);
	scanf("%s",str+1);
	prepare();
	for(int i=1,a,b,c,d,l,r,mid,ret;i<=q;i++){
		read(a),read(b),read(c),read(d);
		l=1,r=std::min(b-a+1,d-c+1),ret=0;
		while(l<=r){
			mid=(l+r)>>1;
			if(check(mid,a,b,c,d)) l=mid+1,ret=mid;
			else r=mid-1;
		}
		printf("%d\n",ret);
	}
	return 0;
}