Description

题目链接

题目大意：给定字符串 $s$，$m$ 次询问 $[a, b]$ 的所有子串和 $s[c...d]$ 的 LCP 的最大值。$|s|, m \le 10^5$。

Solution

考虑二分答案 $m$，问题转化为判断 $[a, b]$ 中是否存在跟 $s[c...c + m - 1]$ 相等的子串。

在后缀树上找到 $c + m - 1$ 对应的点，倍增找到长度大于等于 $m$ 且深度最小的祖先，然后看一下这个祖先的 $\text{endpos}$ 集合里有没有在 $[a + m - 1, b]$ 中的点，用线段树合并实现。

时间复杂度 $O(n \log^2 n)$。

Code

#include <bits/stdc++.h>

template <class T>
inline void read(T &x) {
    x = 0;
    int f = 0;
    char ch = getchar();
    while (!isdigit(ch))    { f |= ch == '-'; ch = getchar(); }
    while (isdigit(ch))     { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    x = f ? -x : x;
    return ;
}

typedef unsigned long long uLL;
typedef long long LL;

constexpr int maxn = 1e5 + 10;

std::vector<int> g[maxn << 1];
int tr[maxn << 1][26], fa[maxn << 1][20];
int len[maxn << 1], ls[maxn << 6], rs[maxn << 6], rt[maxn << 1], t[maxn << 6], pos[maxn];
int n, m, ans, tot = 1, lst = 1, cnt;
char s[maxn];

void modify(int &x, int L, int R, int p, int v) {
    if (!x)    x = ++cnt;
    if (L == R) {
        t[x] += v;
        return ;
    }
    int mid = (L + R) >> 1;
    if (p <= mid)    modify(ls[x], L, mid, p, v);
    else    modify(rs[x], mid + 1, R, p, v);
    t[x] = t[ls[x]] + t[rs[x]];
    return ;
}

int merge(int u, int v, int L, int R) {
    if ((!u) || (!v))    return u + v;
    int w = ++cnt;
    if (L == R) {
        t[w] = t[u] + t[v];
        return w; 
    }
    int mid = (L + R) >> 1;
    ls[w] = merge(ls[u], ls[v], L, mid), rs[w] = merge(rs[u], rs[v], mid + 1, R);
    t[w] = t[ls[w]] + t[rs[w]];
    return w;
}

int query(int x, int L, int R, int l, int r) {
    if (!x)    return 0;
    if (l <= L && R <= r)    return t[x];
    int mid = (L + R) >> 1, res = 0;
    if (l <= mid)    res += query(ls[x], L, mid, l, r);
    if (r > mid)    res += query(rs[x], mid + 1, R, l, r);
    return res;
}

void insert(int x) {
    int p = lst, np = ++tot;
    len[np] = len[p] + 1;
    modify(rt[np], 1, n, len[np], 1);
    for (; p && (!tr[p][x]); p = fa[p][0])    tr[p][x] = np;
    if (!p)    fa[np][0] = 1;
    else {
        int q = tr[p][x];
        if (len[q] == len[p] + 1)    fa[np][0] = q;
        else {
            int nq = ++tot;
            memcpy(tr[nq], tr[q], sizeof(tr[q]));
            len[nq] = len[p] + 1;
            fa[nq][0] = fa[q][0];
            fa[q][0] = fa[np][0] = nq;
            for (; p && tr[p][x] == q; p = fa[p][0])    tr[p][x] = nq;
        }
    }
    lst = np;
    return ;
}

void dfs(int x) {
    for (int i = 1; i <= 18; ++i)    fa[x][i] = fa[fa[x][i - 1]][i - 1];
    for (auto i : g[x]) {
        dfs(i);
        rt[x] = merge(rt[x], rt[i], 1, n);
    }
}

bool check(int a, int b, int c, int mid) {
    if (!mid)    return true;
    int p = pos[c + mid - 1];
    for (int i = 18; i >= 0; --i) {
        if (fa[p][i] && len[fa[p][i]] >= mid) {
            p = fa[p][i];
        }
    }
    return query(rt[p], 1, n, a + mid - 1, b);
}

int main() {
    read(n), read(m);
    scanf("%s", s + 1);
    for (int i = 1; i <= n; ++i)    insert(s[i] - 'a');
    for (int i = 2; i <= tot; ++i)    g[fa[i][0]].push_back(i);
    for (int i = 1, x = 1; i <= n; ++i) {
        x = tr[x][s[i] - 'a'];
        pos[i] = x;
    }
    dfs(1);
    while (m--) {
        int a, b, c, d;
        read(a), read(b), read(c), read(d);
        int l = 0, r = std::min(b - a + 1, d - c + 1), ans = 0;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (check(a, b, c, mid))    ans = mid, l = mid + 1;
            else    r = mid - 1;
        }
        printf("%d\n", ans);
    }
    return 0;
}