题意:求$s[a\ldots b]$的所有子串和$s[c\ldots d]$的最长公共前缀的长度的最大值,多组询问。

其实$s[a\ldots b]$的所有子串与$s[c\ldots d]$的最长公共前缀的长度的最大值等价于以$a\ldots b$开头的后缀与$s[c\ldots d]$的最长公共前缀长度的最大值,仅仅只需要一些转化。

不难发现其实打一发$SA$求出$\text{height}$数组,就可以得到一些想要的东西。

到这里有一个很朴素的暴力就是逐一去求长度然后取最大值,复杂度为$\Theta(mn\log n)$。

考虑二分答案 $\text{mid}$ ,由于 $\text{height}$ 的性质,由 $\text{rank[c]}$ 往左右拓展,必有一段连续的

$\text{height}[l\ldots r]\ge \text{mid}$

只要在这一段$[l\ldots r]$中寻找有无$\text{sa}[i]\in[a,b-mid+1]$即可。

如何快速判断$l,r$,就使用$\text{RMQ}$吧。

搭配上主席树就可以勉强以$\Theta(m\log^2 n)$的复杂度通过此题。

代码实现中$l$可以不取。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
#define ll long long
#define fin(s) freopen(s".in","r",stdin)
#define I inline 
using namespace std;
const int N=1e5+5,mod=998244353,G=3,W=mod-1;
template<class o>I void qr(o &x)
{
    char c=gc;int f=1;x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>I void qw(o x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int sa[N],wa[N],wb[N],wv[N],c[N],n,m,Q;char s[N];
I bool cmp(int *y,int a,int b,int l){return y[a]==y[b]&&y[a+l]==y[b+l];}
void SA()
{
    int *x=wa,*y=wb,*t,m=100;
    for(int i=1;i<=n;i++)++c[x[i]=s[i]-'a'+1];
    for(int i=2;i<=m;i++)c[i]+=c[i-1];
    for(int i=n;i>=1;i--)sa[c[x[i]]--]=i;
    for(int j=1,p=0;p<n;j<<=1,m=p)
    {
        p=0;for(int i=n-j+1;i<=n;i++)y[++p]=i;
        for(int i=1;i<=n;i++)if(sa[i]-j>0)y[++p]=sa[i]-j;
        for(int i=1;i<=m;i++)c[i]=0;
        for(int i=1;i<=n;i++)++c[wv[i]=x[y[i]]];
        for(int i=2;i<=m;i++)c[i]+=c[i-1];
        for(int i=n;i>=1;i--)sa[c[wv[i]]--]=y[i];
        t=x;x=y;y=t;x[sa[1]]=1;p=1;
        for(int i=2;i<=n;i++)
            x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p:++p;
    }
}
int rk[N],height[N];
void gh()
{
    for(int i=1;i<=n;i++)rk[sa[i]]=i;
    for(int i=1,k=0,j;i<=n;height[rk[i++]]=k)
        for(k?k--:k,j=sa[rk[i]-1];s[i+k]==s[j+k];++k);
}
struct HJT{int s,l,r;}t[N*20];int root[N],cnt;
void update(int l,int r,int &x,int y,int pos)
{
    t[x=++cnt]=t[y];++t[x].s;
    if(l==r)return ;
    int mid=l+r>>1;
    if(pos<=mid)update(l,mid,t[x].l,t[y].l,pos);
    else update(mid+1,r,t[x].r,t[y].r,pos);
}
int ask(int l,int r,int L,int R,int x,int y)
{
    if(L<=l&&R>=r)return t[x].s-t[y].s;
    int mid=l+r>>1,val=0;
    if(L<=mid)val+=ask(l,mid,L,R,t[x].l,t[y].l);
    if(R>mid)val+=ask(mid+1,r,L,R,t[x].r,t[y].r);
    return val;
}
int f[18][N],Log[N];
void RMQ()
{
    for(int i=1;i<=n;i++)f[0][i]=height[i],update(1,n,root[i+1],root[i],sa[i]);
    Log[1]=0;for(int i=2;i<=n;i++)Log[i]=Log[i>>1]+1;
    for(int i=1;i<=Log[n-1]+1;i++)
        for(int j=1;j+(1<<i)-1<=n;j++)
            f[i][j]=min(f[i-1][j],f[i-1][j+(1<<(i-1))]);
}
int A,B,C,D;
bool check(int x)
{
    int l=rk[C],r=rk[C]+1;
    for(int i=Log[n-1]+1;~i;i--)
    {
        if(l-(1<<i)>=1&&f[i][l-(1<<i)+1]>=x)l-=(1<<i);
        if(r+(1<<i)<=n&&f[i][r]>=x)r+=(1<<i);
    }
    return ask(1,n,A,B-x+1,root[r],root[l]);
}
int main()
{ 
//    fin("str2");
    qr(n);qr(Q);
    scanf("%s",s+1);
    SA();gh();
    RMQ();
    for(int i=1;i<=Q;i++)
    {
        qr(A),qr(B),qr(C),qr(D);
        int l=0,r=min(B-A+1,D-C+1);
        for(int mid=l+r+1>>1;l<r;mid=l+r+1>>1)
            if(!check(mid))r=mid-1;
            else l=mid;
        qw(l);puts("");
    }
    return 0;
}