二分答案，（具体可见http://blog.****.net/neither_nor/article/details/51669114），然后就是判定问题，sa和sam都可以做，用sam写了一下，先用sam建后缀树，然后用主席树维护right集合就好了，每次判断把对应节点倍增到深度为mid的点，然后看一下他的子树里有没有right在对应区间的点就好了。
（前几天用sa写了一下，bz能A,洛谷一直WA，有空重构吧。。。）
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=,maxm=;
int a,b,c,d,t,pos[maxn],cnt=,cur,fa[maxn],ch[maxn][],dis[maxn],n,m,tot;
char s[maxn];
int add(int c,int p){
cur=++cnt;dis[cur]=dis[p]+;
for(;p&&!ch[p][c];p=fa[p])ch[p][c]=cur;
if(!p)fa[cur]=;
else{
int q=ch[p][c];
if(dis[q]==dis[p]+)fa[cur]=q;
else{
int nt=++cnt;dis[nt]=dis[p]+;
memcpy(ch[nt],ch[q],sizeof(ch[]));
fa[nt]=fa[q];fa[q]=fa[cur]=nt;
for(;p&&ch[p][c]==q;p=fa[p])ch[p][c]=nt;
}
}
return cur;
}
vector<int>tong[maxn];
int root[maxn],siz[maxn],tim,last[maxn*],pre[maxn*],other[maxn*],f[maxn][],dfn[maxn],from[maxn];
void insert(int x,int y){++t;pre[t]=last[x];last[x]=t;other[t]=y;}
void dfs(int x){
siz[x]=;dfn[x]=++tim;from[tim]=x;
for(int i=last[x];i;i=pre[i]){
int v=other[i];
f[v][]=x;dfs(v);
siz[x]+=siz[v];
}
}
int jump(int x,int y){
for(int i=;i>=;--i){
if(dis[f[x][i]]>=y)x=f[x][i];
}
return x;
}
struct node{
int l,r,v;
}tr[maxm];
void build(int pos,int l,int r,int &x){
++tot;tr[tot]=tr[x];x=tot;++tr[x].v;
if(l==r)return;
int mid=l+r>>;
if(pos<=mid)build(pos,l,mid,tr[x].l);
else build(pos,mid+,r,tr[x].r);
}
int qs(int i,int j,int l,int r,int L,int R){
if(r<L||l>R||r<l)return ;
if(l>=L&&r<=R)return tr[j].v-tr[i].v;
int mid=l+r>>;
return qs(tr[i].l,tr[j].l,l,mid,L,R)+qs(tr[i].r,tr[j].r,mid+,r,L,R);
}
int pd(int mid){
int op=jump(pos[c],mid);
return qs(root[dfn[op]-],root[dfn[op]+siz[op]-],,n,a,b-mid+);
}
int main(){
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
int tmp=;
cin>>n>>m;
scanf("%s",s+);
for(int i=n;i>=;--i){
tmp=add(s[i]-'a',tmp);
pos[i]=tmp;
tong[pos[i]].push_back(i);
}
for(int i=;i<=cnt;++i)insert(fa[i],i);dfs();
for(int j=;j<=;++j)
for(int i=;i<=cnt;++i){
f[i][j]=f[f[i][j-]][j-];
}
for(int i=;i<=tim;++i){
int siz=tong[from[i]].size();root[i]=root[i-];
for(int j=;j<siz;++j){
build(tong[from[i]][j],,n,root[i]);
}
}
for(int i=;i<=m;++i){
scanf("%d%d%d%d",&a,&b,&c,&d);
int l=,r=min(d-c+,b-a+),ans=;
while(l<=r){
int mid=l+r>>;
if(pd(mid))ans=mid,l=mid+;
else r=mid-;
}
printf("%d\n",ans);
}
//fclose(stdin);
//fclose(stdout);
//system("pause");
return ;
}
/*
50 1
pnzogoobycwczqfrbylxuwkgmnzlekbcakviijcrjahthagkcn
20 47 8 50
*/