又是传统的 AcWing 没有这题题解环节。
没关系很快就有了。

后缀数组笔记。

看到题目很自然地想到 SA 处理子串问题。
然后怎么搞 $[a,b]$ 的所有子串和 $[c,d]$ 子串的 LCP？
完全不会做啊，先骗 $40$ 分吧。
直接枚举 $[a,b]$ 中选择子串的左端点 $t$，然后相当于是 $[t,n]$ 后缀与 $[c,n]$ 后缀进行匹配，求 LCP。
然后再和 $\min(b-t+1,d-c+1)$ 取 $\min$ 即可。

时间复杂度 $O(nm)$。

首先不难注意到答案是有单调性的，如果 $ans$ 满足条件，那么 $ans-1$ 一定也满足条件。
有单调性一定可以二分，现在考虑如何判定 $ans$ 是否满足条件？
相当于判定 $[a,b-ans+1]$ 是否有一个 $t$，且 $\text{LCP}(t,c) \geq ans$。

注意到如果固定 $c$，LCP 关于 rk 也是有单调性的。
可以转化为二分出 $[l,r]$ 满足 $\forall x \in [l,r]$ 都有 $\text{LCP}(x,c) \geq ans$，且 $[l,r]$ 是极长的。
然后相当于求 $[a,b-ans+1]$ 内有没有 $[l,r]$ 的点。
二维数点！可持久化线段树秒了！

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m;
char s[N];

int sa[N], rk[N], cnt[N], x[N << 1], y[N << 1];
void init_SA() {
    int v = 128;
    for (int i = 0; i <= v; i++) cnt[i] = 0;
    for (int i = 1; i <= n; i++) ++cnt[x[i] = (int)s[i]];
    for (int i = 1; i <= v; i++) cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; i--) sa[ cnt[x[i]]-- ] = i;

    for (int len = 1; ; len <<= 1) {
        int tot = 0;
        for (int i = n - len + 1; i <= n; i++) y[++tot] = i;
        for (int i = 1; i <= n; i++)
            if (sa[i] > len) y[++tot] = sa[i] - len;

        for (int i = 0; i <= v; i++) cnt[i] = 0;
        for (int i = 1; i <= n; i++) ++cnt[x[i]];
        for (int i = 1; i <= v; i++) cnt[i] += cnt[i - 1];
        for (int i = n; i >= 1; i--) sa[ cnt[x[y[i]]]-- ] = y[i], y[i] = 0;

        swap(x, y), tot = 0;
        for (int i = 1; i <= n; i++) {
            if (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + len] == y[sa[i - 1] + len]) x[sa[i]] = tot;
            else x[sa[i]] = ++tot;
        }
        v = tot;
        if (v == n) break;
    }
}

int ht[N];
void init_height() {
    for (int i = 1; i <= n; i++) rk[sa[i]] = i;
    for (int i = 1, j = 0, now = 0; i <= n; i++) {
        if (rk[i] == 1) { ht[rk[i]] = 0; continue; }
        j = sa[rk[i] - 1], now = max(0, now - 1);
        while (i + now <= n && j + now <= n && s[i + now] == s[j + now]) now++;
        ht[rk[i]] = now;
    }
}

int mn[N][18], lg[N];
void init_ST() {
    for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
    for (int i = 1; i <= n; i++) mn[i][0] = ht[i];
    for (int i = 1; i <= 17; i++)
        for (int j = 1; j + (1 << i) - 1 <= n; j++)
            mn[j][i] = min(mn[j][i - 1], mn[j + (1 << i - 1)][i - 1]);
}
int askmn(int l, int r) {
    int len = lg[r - l + 1];
    return min(mn[l][len], mn[r - (1 << len) + 1][len]);
}
int LCP(int a, int b) {
    if (a == b) return n - sa[a] + 1;
    return askmn(a + 1, b);
}

int rt[N], tot = 0;
struct Tree { int ls, rs, sum; } tr[N << 5];
void change(int &u, int l, int r, int x) {
    tr[++tot] = tr[u], u = tot, tr[u].sum++;
    if (l == r) return;
    int mid = l + r >> 1;
    if (x <= mid) change(tr[u].ls, l, mid, x);
    else change(tr[u].rs, mid + 1, r, x);
}
int query(int u, int l, int r, int ql, int qr) {
    if (!u || ql > qr) return 0;
    if (ql <= l && qr >= r) return tr[u].sum;
    int mid = l + r >> 1, res = 0;
    if (ql <= mid) res = query(tr[u].ls, l, mid, ql, qr);
    if (qr > mid) res += query(tr[u].rs, mid + 1, r, ql, qr);
    return res;
}

bool check(int a, int b, int c, int x) {    // [a, b] 是否存在一个 t 满足 LCP(t, c) >= x
    int l, r, L, R;   //首先二分出 LCP 合法的 rk 区间 [L, R]
    l = 1, r = rk[c];
    while (l < r) {
        int mid = l + r >> 1;
        if (LCP(mid, rk[c]) >= x) r = mid;
        else l = mid + 1;
    }
    L = l;

    l = rk[c], r = n;
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (LCP(rk[c], mid) >= x) l = mid;
        else r = mid - 1;
    }
    R = l;

    return ( query(rt[b], 1, n, L, R) - query(rt[a - 1], 1, n, L, R) ) > 0;
}

int main() {
    scanf("%d%d", &n, &m);
    scanf("\n %s\n ", s + 1);
    init_SA(), init_height(), init_ST();
    for (int i = 1; i <= n; i++) rt[i] = rt[i - 1], change(rt[i], 1, n, rk[i]);

    // for (int i = 1; i <= n; i++) cout << ht[i] << ' '; puts("");
    while (m--) {
        int a, b, c, d; scanf("%d%d%d%d", &a, &b, &c, &d);
        int l = 0, r = min(b - a + 1, d - c + 1);
        while (l < r) { //二分答案
            int mid = l + r + 1 >> 1;
            if (check(a, b - mid + 1, c, mid)) l = mid;
            else r = mid - 1;
        }
        printf("%d\n", l);
    }
    return 0;
}