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;
}