DDOSvoid's Blog

Luogu P6640 [BJOI2020] 封印

发表于 分类于
本文字数： 2.4k 阅读时长 ≈ 2 分钟

题目描述

https://www.luogu.com.cn/problem/P6640

简要题意：给定两个字符串 $S,T$ 和 $q$ 次询问，每次询问 $S[l\cdots r]$ 和 $T$ 的最长公共子串长度

$|S|,|T|\le 2\times 10^5,q\le 2\times 10^5$

Solution

我们考虑对于 $T$ 建 $SAM$，然后对于所有 $pre(S,i)$ 我们求出于 $T$ 的最长公共后缀的长度 $len_i$，这个过程就是拿 $S$ 在 $T$ 的 $SAM$ 上做匹配

对于一次询问，根据 $len_i$，我们能够得到 $pre(S,i)$ 的与 $T$ 匹配的最长公共后缀的左端点 $L_i=i-len_i+1$，

我们的答案是 $max\lbrace i-max\lbrace L_i,l\rbrace+1\rbrace,i\in[l,r]$，注意到 $L_i$ 是单增的，所以可以二分出 $L_i$ 比 $l$ 大的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <iostream>
#include <cstring>
#include <vector>
#define maxn 200010
#define Maxn 400010
#define ll long long
using namespace std;

struct SAM {
    int sz, L, l, nxt[26]; 
} T[Maxn]; int f[Maxn], top, last, rt;
void init_SAM() {
    for (int i = 1; i <= top; ++i) {
        T[i].sz = T[i].L = T[i].l = 0;
        fill(T[i].nxt, T[i].nxt + 26, 0); 
    }
    rt = last = top = 1; 
    T[rt].L = T[rt].l = f[rt] = 0;
}

void extend(int ch) {
    int np = ++top, p = last; last = np;
    T[np].L = T[p].L + 1; T[np].sz = 1;
    while (p && !T[p].nxt[ch]) T[p].nxt[ch] = np, p = f[p];
    if (!p) return f[np] = rt, void();
    int q = T[p].nxt[ch];
    if (T[q].L - 1 == T[p].L) f[np] = q;
    else {
        int nq = ++top; T[nq].L = T[p].L + 1; f[nq] = f[q];
        for (int i = 0; i < 26; ++i) T[nq].nxt[i] = T[q].nxt[i];
        while (p && T[p].nxt[ch] == q) T[p].nxt[ch] = nq, p = f[p];
        f[np] = f[q] = nq;
    } 
}

int n, m, q, L[maxn];
char s[maxn], t[maxn];

int Log[maxn], st[maxn][21];
void init_st() { Log[0] = -1;
    for (int i = 1; i <= n; ++i) Log[i] = Log[i >> 1] + 1, st[i][0] = i - L[i] + 1; 
    for (int j = 1; j <= 20; ++j)
        for (int i = 1; i + (1 << j) - 1 <= n; ++i)
            st[i][j] = max(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
}

int query(int l, int r) {
    if (l > r) return 0; 
    int k = Log[r - l + 1];
    return max(st[l][k], st[r - (1 << k) + 1][k]);
}


int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> s + 1 >> t + 1; init_SAM();
    n = strlen(s + 1); m = strlen(t + 1); 
    for (int i = 1; i <= m; ++i) extend(t[i] - 'a');
    int p = rt, len = 0; 
    for (int i = 1; i <= n; ++i) {
        int ch = s[i] - 'a';
        if (T[p].nxt[ch]) p = T[p].nxt[ch], ++len;
        else {
            while (p && !T[p].nxt[ch]) p = f[p];
            if (!p) p = rt, len = 0;
            else len = T[p].L + 1, p = T[p].nxt[ch];
        }
        L[i] = i - len + 1;
    } 
    cin >> q; init_st();
    for (int i = 1; i <= q; ++i) {
        int x, y; cin >> x >> y;
        int l = x, r = y, mid, ans = y + 1; 
        while (l <= r) {
            mid = l + r >> 1;
            if (L[mid] >= x) ans = mid, r = mid - 1;
            else l = mid + 1; 
        }
        cout << max(ans - x, query(ans, y)) << "\n";
    }
    return 0;
}