Visits: 241

LOJ3298 「BJOI2020」封印

新鲜出炉的 2020 省选题嗷。

首先对于每个 $s$ 的后缀 $i$ 找到其与 $t$ 的最长公共子串长度 $f_i$，这个把 $s$ 和 $t$ 隔一个字符并起来做 SA，然后从前往后从后往前扫一遍即可。

对于每个询问，相当于求 $\max_{i=l}^r \min(f_i, r – i + 1)$。

注意到 $f_i \ge f_{i-1} – 1$，因此 $\min(f_i, r – i + 1)$ 取到 $r-i+1$ 的位置一定是一个后缀。

二分到决策交换点，然后求一个 RMQ 即可，时间复杂度 $\mathcal O(n \log n)$。

const int N = 4e5 + 7, inf = 1e9;
int n, m, q, f[N][21];
char s[N], t[N];

struct SA {
    char s[N];
    int n, m = 127, sa[N], rk[N<<1|1], tp[N<<1|1], tx[N], he[N];
    inline void sort() {
        for (int i = 1; i <= m; i++) tx[i] = 0;
        for (int i = 1; i <= n; i++) ++tx[rk[i]];
        for (int i = 1; i <= m; i++) tx[i] += tx[i-1];
        for (int i = n; i; i--) sa[tx[rk[tp[i]]]--] = tp[i]; 
    }
    inline bool pd(int i, int j, int k) {
        return tp[i] == tp[j] && tp[i+k] == tp[j+k];
    }
    inline void main() {
        for (int i = 1; i <= n; i++) rk[i] = s[i], tp[i] = i;
        sort();
        for (int k = 1, p = 0; p < n; k <<= 1, m = p) {
            p = 0;
            for (int i = 1; i <= k; i++) tp[++p] = n - k + i;
            for (int i = 1; i <= n; i++)
                if (sa[i] > k) tp[++p] = sa[i] - k;
            sort(), swap(rk, tp), rk[sa[1]] = p = 1;
            for (int i = 2; i <= n; i++)
                rk[sa[i]] = p += !pd(sa[i], sa[i-1], k); 
        }
        for (int i = 1, p = 0; i <= n; i++) {
            if (p) --p;
            int j = sa[rk[i]-1];
            while (s[i+p] == s[j+p]) ++p;
            he[rk[i]] = p;
        }
    }
} sa;

inline int ask(int l, int r) {
    if (l > r) return 0;
    int w = log2(r - l + 1);
    return max(f[l][w], f[r-(1<<w)+1][w]);
}

int main() {
    rds(s, n), rds(t, m);
    for (int i = 1; i <= n; i++) sa.s[i] = s[i];
    sa.s[n+1] = 1;
    for (int i = 1; i <= m; i++) sa.s[i+n+1] = t[i];
    sa.n = n + m + 1;
    sa.main();
    for (int i = 1, k = inf; i <= sa.n; i++) {
        k = min(k, sa.he[i]);
        if (sa.sa[i] <= n && k != inf) f[sa.sa[i]][0] = k;
        else k = inf;
    }
    for (int i = sa.n, k = inf; i; i--) {
        if (sa.sa[i] <= n && k != inf) f[sa.sa[i]][0] = max(f[sa.sa[i]][0], k);
        else k = inf;
        k = min(k, sa.he[i]);
    }
    int w = log2(n);
    for (int i = 0; i < w; i++)
        for (int l = 1; l + (1 << (i + 1)) - 1 <= n; l++)
            f[l][i+1] = max(f[l][i], f[l+(1<<i)][i]);
    rd(q);
    for (int i = 1, l, r; i <= q; i++) {
        rd(l, r);
        int L = l - 1, R = r;
        while (L < R) {
            int D = (L + R + 1) >> 1;
            if (f[D][0] < r - D + 1) L = D;
            else R = D - 1;
        }
        print(max(r - L, ask(l, L)));
    }
    return 0;
}