后缀数组

模板

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
namespace SA {
int n, m, sa[maxn], h[maxn], c[maxn], x[maxn], y[maxn];
void rsort() {
for (int i = 1; i <= m; i++) c[i] = 0;
for (int i = 1; i <= n; i++) c[x[i]]++;
for (int i = 1; i <= m; i++) c[i] += c[i - 1];
for (int i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i];
}
int cmp(int i, int j, int k) {
int a = i + k > n ? -1 : y[i + k];
int b = j + k > n ? -1 : y[j + k];
return y[i] == y[j] && a == b;
}
void build(int nn, char* s) {
n = nn; m = 255; // important
for (int i = 1; i <= n; i++) x[i] = s[i], y[i] = i;
rsort();
for (int k = 1, p; k <= n; k += k, m = p) {
p = 0;
for (int i = n; i > n - k; i--) y[++p] = i;
for (int i = 1; i <= n; i++) if (sa[i] > k) y[++p] = sa[i] - k;
rsort();
for (int i = 1; i <= n; i++) swap(x[i], y[i]);
x[sa[1]] = p = 1;
for (int i = 2; i <= n; i++) x[sa[i]] = cmp(sa[i], sa[i - 1], k) ? p : ++p;
}
for (int i = 1; i <= n; i++) x[sa[i]] = i;
for (int i = 1, k = 0; i <= n; i++) {
if (k) k--;
int j = sa[x[i] - 1];
while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) k++;
h[x[i]] = k;
}
}
}

LCP 模板

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
namespace SA {
int n, m, sa[maxn], h[maxn], c[maxn], x[maxn], y[maxn];
void rsort() {
for (int i = 1; i <= m; i++) c[i] = 0;
for (int i = 1; i <= n; i++) c[x[i]]++;
for (int i = 1; i <= m; i++) c[i] += c[i - 1];
for (int i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i];
}
int cmp(int i, int j, int k) {
int a = i + k > n ? -1 : y[i + k];
int b = j + k > n ? -1 : y[j + k];
return y[i] == y[j] && a == b;
}
int dp[maxn][21];
void build(int nn, char* s) {
n = nn; m = 255;
for (int i = 1; i <= n; i++) x[i] = s[i], y[i] = i;
rsort();
for (int k = 1, p; k <= n; k += k, m = p) {
p = 0;
for (int i = n; i > n - k; i--) y[++p] = i;
for (int i = 1; i <= n; i++) if (sa[i] > k) y[++p] = sa[i] - k;
rsort();
for (int i = 1; i <= n; i++) swap(x[i], y[i]);
x[sa[1]] = p = 1;
for (int i = 2; i <= n; i++) x[sa[i]] = cmp(sa[i], sa[i - 1], k) ? p : ++p;
}
for (int i = 1; i <= n; i++) x[sa[i]] = i;
for (int i = 1, k = 0; i <= n; i++) {
if (k) k--;
int j = sa[x[i] - 1];
while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) k++;
h[x[i]] = k;
}
for (int i = 1; i <= n; i++) dp[i][0] = h[i];
for (int j = 1; j < 21; j++) {
for (int i = 1; i + (1 << j) <= n + 1; i++) {
dp[i][j] = min(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
}
}
}
int qlcp(int l, int r) {
if (l == r) return n - l + 1;
l = x[l]; r = x[r];
if (l > r) swap(l, r);
l++;
int k = 0; while ((1 << (k + 1)) <= r - l + 1) k++;
return min(dp[l][k], dp[r - (1 << k) + 1][k]);
}
}

注意

  1. 下标从 $1$ 开始。

  2. 每个字符的值域范围。

定义

  1. $sa[n]$ : 后缀排序后,排名第 $i$ 个串的开始下标。
  2. $rk[n]$ : 原串第 $i$ 个后缀排过序后的名次。
  3. $sa[n]$ 和 $rk[n]$ 互为逆运算,$rk[sa[i]]=sa[rk[i]]=i$。
  4. $LCP$ : 最长公共前缀。
  5. $height[rk[i]] \ge height[rk[i-1]] - 1$。
  6. $height[i]$ = $LCP(sa[i - 1],sa[i])$ ($2 \le i \le n$)。

一个串的经典问题

本质不同子串个数

${n(n+1) \over 2}-\sum_{i=2}^n height[i]$。

可重叠的最长重复子串

$height$ 数组最大值。

不可重叠的最长重复子串

二分答案。

当前二分到 $mid$, 将 $height$ 数组中连续大于等于 $mid$ 的位置划分进一块,一个块内求出现位置的最大值和最小值,如果相差大于等于 $mid$,即代表出现了一段不重叠的重复子串。

1
2
3
4
5
6
7
8
9
10
11
int check(int len) {
int mx = sa[1], mn = sa[1];
for (int i = 2; i <= n; i++) {
if (h[i] >= len) {
mn = min(mn, sa[i]);
mx = max(mx, sa[i]);
if (mx - mn >= len) return 1;
} else mx = sa[i], mn = sa[i];
}
return 0;
}

循环节最多的子串

枚举循环节大小 $len$,求 $s[1],s[1+len], s[1+2\cdot len], \dots$,相邻两个的 $LCP$,设 $LCP$ 为 $x$,则循环节个数至少为 ${x \over len} + 1$,再特判一下剩余的 $len - x \bmod len$ 个字符,将 $s[1+k\cdot len]$ 向前推这么多能否构成一个更多的循环节。

两个串的经典问题

最长公共子串

将两个串用一个小字符连起来,建一个后缀数组。

$ans=max(height[i])$,满足 $sa[i]$ 和 $sa[i-1]$ 不在同一个串内。

多个串的经典问题

将多个串用不同的未出现字符连成一个(注意值域大小)。

出现在至少 $k$ 个串中的最长子串

二分答案,对 $height$ 分块,判断一个块内是否出现 $k$ 次。

  • 本文作者: XLor
  • 本文链接: https://xlor.cn/2018/10/sa/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!