Comet-OJ-3980 【字符串】

发表于 | 更新于 | 分类于 ，

复习一波 $SA$ (后缀数组)

$\Large\mathcal{Description}$

给定一个字符串 $s$。

有 $q$ 次询问，每次询问给定一个字符串 $t$ ，求最小的整数 $k$，满足以下两个条件：

  1. $0 \leqslant k \leqslant |s| - |t|$
  2. $s_{[k, k + |t| - 1]}$ 的字典序大于 $t$

数据范围 $:$ $1 \leqslant |s| \leqslant 2 \times 10^5$，$1 \leqslant q \leqslant 5000$，$\sum |t| \leqslant 2 \times 10^5$

$\Large\mathcal{Solution}$

首先，一个字符串的任何子串肯定是该字符串的一个后缀的前缀。

所以，我们对字符串的后缀进行处理。各种数据结构，这里介绍 $SA$ 的做法。

你们肯定都会 $SAM$，幼小的我只会 $SA$

我们熟练地把所有串都连在一起，串与串之间用一些大于字符串中所有字符的奇怪字符隔开。(用 $SA$ 处理多个串的基本套路)

跑一遍 $SA$ 后，我们就得到了 $sa$ 数组(即排名为 $i$ 的后缀的起始位置下标)

然后从大到小枚举后缀即可。

$\Large\mathcal{Code}$

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

template <typename Tp>
inline void read(Tp &x) {
    x = 0;
    bool f = true; char ch = getchar();
    for ( ; ch < '0' || ch > '9'; ch = getchar()) f ^= ch == '-';
    for ( ; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + (ch ^ 48);
    x = f ? x : -x;
}

const int N = 5e5 + 7, Q = 5e3 + 7;

int sa[N], x[N], tot[N], y[N], len[Q], ans[Q], pos[N], n;
std::string s;

inline void SA() {
    int m = 'z' + 1;
    for (int i = 1; i <= n; ++i) x[i] = s[i], ++tot[x[i]];
    for (int i = 1; i <= m; ++i) tot[i] += tot[i - 1];
    for (int i = n; i; --i) sa[tot[x[i]]--] = i;
    for (int k = 1; k <= n; k <<= 1) {
        int num = 0;
        for (int i = n - k + 1; i <= n; ++i) y[++num] = i;
        for (int i = 1; i <= n; ++i) if (sa[i] > k) y[++num] = sa[i] - k;
        for (int i = 1; i <= m; ++i) tot[i] = 0;
        for (int i = 1; i <= n; ++i) ++tot[x[i]];
        for (int i = 1; i <= m; ++i) tot[i] += tot[i - 1];
        for (int i = n; i; --i) sa[tot[x[y[i]]]--] = y[i], y[i] = 0;
        std::swap(x, y);
        num = 0;
        for (int i = 1; i <= n; ++i)
            x[sa[i]] = i != 1 && y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? num : ++num;
        if (num == n) return;
        m = num;
    }
}

int main() {
    int q;
    read(q);
    std::cin >> s;
    int l = s.length(); n = l;
    s = ' ' + s;
    for (int i = 1; i <= q; ++i) {
        std::string t;
        std::cin >> t;
        len[i] = t.length();
        s += (char)('z' + 1), ++n;
        pos[n + 1] = i;
        s += t, n += len[i];
    }
    SA();
    int minx = n;
    for (int i = n; i; --i) {
        if (sa[i] <= l) minx = std::min(minx, sa[i]);
        else if (pos[sa[i]] && minx + len[pos[sa[i]]] - 1 <= l) ans[pos[sa[i]]] = minx;
    }
    for (int i = 1; i <= q; ++i) printf("%d\n", ans[i] - 1);
    return 0;
}