除了 hack 都过不去，sam 和线段树部分直接粘的 CF1037H 的

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>

#define N 200001

using namespace std;
string s,t;
int slen,q;

int tcnt,rt[N],edp[N];
struct Tree { int ls,rs; }tr[N<<5];

void build(int &x,int l,int r,int id) {
    if (!x) x=++tcnt;
    if (l==r) return;
    int mid=(l+r>>1);
    if (mid>=id) build(tr[x].ls,l,mid,id);
    else build(tr[x].rs,mid+1,r,id);
}

int merge(int x,int y,int l,int r) {
    if (!x or !y) return x|y;
    int rt=++tcnt;
    if (l==r) return rt;
    int mid=(l+r>>1);
    tr[rt].ls=merge(tr[x].ls,tr[y].ls,l,mid);
    tr[rt].rs=merge(tr[x].rs,tr[y].rs,mid+1,r);
    return rt;
}

bool ask(int x,int l,int r,int L,int R) {
    if (!x or R<L) return 0;
    if (L<=l and r<=R) return 1;
    int mid=(l+r>>1); bool res=0;
    if (L<=mid) res|=ask(tr[x].ls,l,mid,L,R);
    if (R>mid) res|=ask(tr[x].rs,mid+1,r,L,R);
    return res;
}

int tot=1,np=1,len[N],fail[N],ch[N][26];

void ins(int c,int id) {
    int p=np; len[edp[id]=np=++tot]=len[p]+1,build(rt[np],1,slen,id);
    while (p and !ch[p][c]) ch[p][c]=np,p=fail[p];
    if (!p) fail[np]=1;
    else {
        int q=ch[p][c];
        if (len[q]==len[p]+1) fail[np]=q;
        else {
            int nq=++tot;
            fail[nq]=fail[q],len[nq]=len[p]+1;
            fail[np]=fail[q]=nq;
            memcpy(ch[nq],ch[q],sizeof ch[q]);
            while (p and ch[p][c]==q) ch[p][c]=nq,p=fail[p];
        }
    }
}

int cnt,head[N],fa[N][21];
struct Node { int to,nxt; }e[N];

void add(int u,int v) { e[++cnt]=Node{v,head[u]},head[u]=cnt; }

void dfs(int u) {
    fa[u][0]=fail[u];
    for (int i=1;i<=20;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
    for (int i=head[u];i;i=e[i].nxt) {
        int v=e[i].to;
        dfs(v);
        rt[u]=merge(rt[u],rt[v],1,slen);
    }
}

bool check(int l1,int r1,int r2,int mid) {
    int p=edp[r2];
    for (int i=20;i;i--)
        while (len[fa[p][i]]>=mid) p=fa[p][i];
    return ask(rt[p],1,slen,l1+mid-1,r1);
}

int main() {
    scanf("%d%d",&slen,&q);
    cin>>s;
    reverse(s.begin(),s.end());
    s=" "+s;
    for (int i=1;i<=slen;i++) ins(s[i]-'a',i);
    for (int i=2;i<=tot;i++) add(fail[i],i);
    dfs(1);
    while (q--) {
        int l1,r1,l2,r2;
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        l1=slen-l1+1,r1=slen-r1+1,l2=slen-l2+1,r2=slen-r2+1;
        swap(l1,r1),swap(l2,r2);
        int l=1,r=min(r2-l2+1,r1-l1+1),res=0;
        while (l<=r) {
            int mid=(l+r>>1);
            if (check(l1,r1,r2,mid)) l=mid+1,res=mid;
            else r=mid-1;
        }
        printf("%d\n",res);
    }
    return 0;
}