后缀数组学习笔记

后缀数组是解决字符串问题的有力工具。

“后缀数组哪里难？后缀难还是数组难？”

前置知识

基数排序

这玩意挺多写法的，我的数字排序的基数排序板子（洛谷模板题比 std::sort 要快）和后缀数组要用的并不一样。理解下原理就好。

倍增法求后缀数组

实现后缀数组的方式主要有两种：倍增法 $O(n \log n)$ 和 DC3 法 $O(n)$。由于我太菜所以只学倍增法。

变量定义

$S$：原串，下标从 $1$ 到 $n$。

$\mathrm{Suf}_i$：$S_{i \dots n}$，即从位置 $i$ 开始的后缀；$\mathrm{Suf}_{i, k}$：$S_{i, i + 2^k - 1}$。

$\mathrm{Rank}_i$：$\mathrm{Suf}_i$ 的排名；$\mathrm{Rank}_{i, k}$：$\mathrm{Suf}_{i, k}$ 的排名。

sa[i]：排名为 $i$ 的后缀的位置。

rk[i]：$\mathrm{Rank}_{i}$。

t[i]：基数排序第二关键字为 $i$ 的后缀的位置。

c[i]：基数排序辅助数组，$i$ 号元素出现次数。

算法流程

目标：对于所有 $\mathrm{Suf}_i$ 排序。

令第 $k$ 个阶段为所有 $\mathrm{Suf}_{i, k}$ 已排序，则目标为 $k \to O( \log n)$，问题转化为如何对 $\mathrm{Suf}_{i, k + 1}$ 排序。

注意到 $\mathrm{Suf}_{i, k + 1} = \mathrm{Suf}_{i, k} + \mathrm{Suf}_{i + 2^k, k}$。要比较 $\mathrm{Suf}_{a, k + 1}$ 和 $\mathrm{Suf}_{b, k + 1}$，即比较 $\mathrm{Suf}_{a, k} + \mathrm{Suf}_{a + 2^k, k}$ 和 $\mathrm{Suf}_{b, k} + \mathrm{Suf}_{b + 2^k, k}$。因此 $\mathrm{Suf}_{i, k + 1}$ 可以看作二元组 $(\mathrm{Rank}_{i, k}, \mathrm{Rank}_{i + 2^k, k})$ 进行排序。

初始时 $\mathrm{Suf}_{i, 0} \ (S_i)$ 一般可以看作二元组 $(S_i, i)$。

Height 数组

如果你是在复习看到这里，一定要扔下任何事情认真读。这里写得非常非常绕。

定义 Height 数组 H[i] 表示排名为 $i$ 的后缀和排名为 $i - 1$ 的后缀的最长前缀的长度，即 $\operatorname{LCP}(\mathrm{sa}_i, \mathrm{sa}_{i - 1})$。

前置结论

对于一个位置 $i \ (i > 1)$，$\operatorname{LCP}(i, i - 1) \ge \operatorname{LCP}(i, j) \ (1 \le j < i)$。也就是说，相邻的后缀的 $\operatorname{LCP}$ 最长。
- 这个直接反证法即可。如果存在 $\operatorname{LCP}$ 更长的后缀，那它的排名应当更接近。
H[rk[i]] >= H[rk[i - 1]] - 1
- 证明：当 $H_{\mathrm{Rank}_{i - 1}} \le 1$ 时显然成立。否则，设 $\mathrm{Rank}_j = \mathrm{Rank}_{i - 1} - 1$，那么将有 $\mathrm{Rank}_{j + 1} < \mathrm{Rank}_i$ 且 $\operatorname{LCP}(i, k + 1) = H_{i - 1} - 1$。由结论 1 得 $H_i \ge H_{i - 1} - 1$。

计算

有了这个结论，计算就很容易了。维护一个 $p$，$p$ 最多自增 $O(n)$ 次，复杂度是 $O(n)$ 的。

模板

namespace SA {
  arr c, rk, sa, t, H;
  int N, M;

  void radixSort() {
    memset(c + 1, 0, sizeof(int) * M);
    for (int i = 1; i <= N; ++i)
      ++c[rk[i]];
    for (int i = 2; i <= M; ++i)
      c[i] += c[i - 1];
    for (int i = N; i; --i)
      sa[c[rk[t[i]]]--] = t[i];
  }

  void sufSort(const char *s) {
    M = 'z' - '0' + 1; // the size of charset
    for (int i = 1; i <= N; ++i)
      rk[i] = s[i] - '0' + 1, t[i] = i;
    radixSort();
    M = 0;
    for (int w = 1; M < N; w <<= 1) {
      M = 0;
      for (int i = N - w + 1; i <= N; ++i)
        t[++M] = i;
      for (int i = 1; i <= N; ++i)
        if (sa[i] > w) t[++M] = sa[i] - w;
      radixSort();
      memcpy(t + 1, rk + 1, sizeof(int) * N);
      rk[sa[1]] = M = 1;
      for (int i = 2; i <= N; ++i)
        rk[sa[i]] = (t[sa[i - 1]] == t[sa[i]] && t[sa[i - 1] + w] == t[sa[i] + w]) ? M : ++M;
    }

    for (int i = 1, j = 0; i <= N; ++i) {
      if (rk[i] == 1) continue;
      while (s[i + j] == s[sa[rk[i] - 1] + j]) ++j;
      H[rk[i]] = j;
      if (j) --j;
    }
  }
} // SA
using namespace SA;

应用

两个后缀的最长公共前缀

对于两个位置 $x, y \ (x < y)$，$\operatorname{LCP}(x, y) = \min_{i = \mathrm{Rank}_{x + 1}}^{ \mathrm{Rank}_y} H_i$。

这个可以用 ST 表实现 $O(1)$ 查询。

可重叠最长重复子串

求最长的子串使得其至少出现了 $2$ 次，不同出现次数之间可以重叠。

这个就是 $\max_{i = 1}^n \{ H_i \}$ 了。

可重叠 $k$ 次最长重复子串

求最长的子串使得其至少出现了 $k$ 次，不同出现次数之间可以重叠。

先考虑二分这个答案 $l$，发现 Height 数组大于等于 $l$ 的位置形成了若干个联通块，$O(n)$ check 即可。

POJ3261 code

wucstdio 说连二分都不需要，我是完全不懂哦

不可重叠最长重复子串

求最长的子串使得其至少出现了 $2$ 次，不同出现次数之间不能重叠。

还是二分一个答案 $l$，在 check 的时候判断一下每个连通块中的位置极差是否大于等于 $l$ 即可。注意细节。

POJ1743 code

不同子串的个数

如果 $H_i = l$，那么长度为 $1 \sim l$ 的所有前缀都会被多算一次，答案减去 $H_i$。总答案为 $n(n + 1) / 2 - \sum_{i = 1}^n{H_i}$。

最长公共子串

给定两个字符串 $S, T, n = |S|, m = |T|$，求它们的最长公共子串。

把两个串拼在一起，中间加一个特殊字符隔开。那么要求的就是

$\max_{i \in [1, n], j \in [n + 2, n + m + 1]}{ \operatorname{LCP}(i, j)}$

取到这个最大值的一定是相邻的后缀，枚举 $i$ 更新答案。

POJ2217 code

最长回文子串

~~这个 Manacher 就可以线性做~~

把这个串取反接到原串后面。

枚举中心点，一个回文子串就是两个位置的 $\operatorname{LCP}$。

~~这样用后缀数组 + ST 表就可以做到 $O(n \log n)$ 的优秀复杂度~~