后缀数组学习笔记

定义

后缀数组是什么？

（下文用 \(Suf_S[i]\) 表示 \(S[i, i + 1, \cdots, |S|]\)，对 \(Suf_T\) 同理。并用 \(S[l, r]\) 表示 \(S[l, l + 1, \cdots, r]\)，对 \(T[l, r]\) 同理）

后缀数组包含两个数组 \(rk, sa\)。

• \(rk[i]\) 表示后缀 \(Suf_S[i]\) 排序后的排名。
• \(sa[i]\) 表示排名为 \(i\) 的后缀的编号。

显然有 \(rk[sa[i]] = sa[rk[i]] = i\)。

求法

倍增 \(O(n \log^2 n)\)。

对于第 \(i + 1\) 次排序，考虑求出长度为 \(2^i\) 的所有子串的排名，并将排名放入 \(rk_i\) 数组。求 \(rk_i\) 的方法是：先求出 \(rk_{i - 1}\) 数组，接着对于子串 \(S[l, l + 2^i - 1]\)，将 \(rk_{i - 1}[l]\) 作为第一关键字，\(rk_{i - 1}[l + 2^{i - 1}]\) 作为第二关键字排序，排序后的编号数组即为 \(rk_i\)。

特别地，对于第 \(1\) 次排序，直接按字符排序即可。而对于 \(l + 2^i - 1 > n\) 的子串，其 \(rk_i[l]\) 视作 \(-\infty\)。

用 sort 可以做到 \(O(n \log^2 n)\)。code:

rep(i, 1, n) sa[i] = i, rk[i] = s[i];
for (int len = 1; len < n; len <<= 1) {
  auto cmp = [&](auto x, auto y) {return rk[x] == rk[y] ? rk[x + len] < rk[y + len] : rk[x] < rk[y];};
  sort(sa + 1, sa + 1 + n, cmp);
  int p = 0;
  rep(i, 1, n) {
    if (!cmp(sa[i], sa[i - 1]) && !cmp(sa[i - 1], sa[i])) o_rk[sa[i]] = p;
    else o_rk[sa[i]] = ++p;
  }
  copy(o_rk + 1, o_rk + 1 + n, rk + 1);
}
rep(i, 1, n) cout << sa[i] << ' ';

基数排序优化 \(O(n \log n)\)

先扯扯基数排序是什么。

基数排序

考虑比较两个字符串的大小，可以将一个字符串拆成 \(k\) 个关键字。那么对于字符串 \(a, b\)，他们比较方式为：

• 首先若 \(a\) 和 \(b\) 的长度不相同，那么在长度短的字符串后面补上若干个 \(-\infty\)。接着进入第一个关键字的比较。
• 若 \(a_0 \ne b_0\)：若 \(a_0 < b_0\) 则 \(a\) 更小，否则 \(b\) 更小。否则 \(a_0 = b_0\)，进入下一个关键字的比较。
• 若 \(a_1 \ne b_1\)：若 \(a_1 < b_1\) 则 \(a\) 更小，否则 \(b\) 更小。否则 \(a_1 = b_1\)，进入下一个关键字的比较。
  \(\cdots\)
• 如果到最后都没有分出大小，则 \(a = b\)。

考虑把这种方式用在整数比较上。把整数拆成若干个关键字的集合，可以把整数的每 \(6\) 位定成一个关键字。

如果是对序列 \(a_1, a_2, \cdots, a_n\) 排序，对每个关键字桶排序即可。code:

const int M = 1E5;
copy(a + 1, a + 1 + n, b + 1);
rep(i, 1, n) ++cnt[b[i] % M];
re(i, 1, M) cnt[i] += cnt[i - 1];
per(i, n, 1) a[cnt[b[i] % M]--] = b[i];
copy(a + 1, a + 1 + n, b + 1);
fill(cnt, cnt + M, 0);
rep(i, 1, n) ++cnt[b[i] / M];
re(i, 1, M) cnt[i] += cnt[i - 1];
per(i, n, 1) a[cnt[b[i] / M]--] = b[i];

在这里基数排序可以替代 sort，因为基数排序本来就是处理多关键字排序的利器，这里恰巧是双关键字排序。

复杂度变为 \(O(n \log n)\)。code:

rep(i, 1, n) sa[i] = i, rk[i] = s[i], ++cnt[rk[i]];
int m = 127;
rep(i, 1, m) cnt[i] += cnt[i - 1];
per(i, n, 1) sa[cnt[rk[i]]--] = i;
int p = 0;
rep(i, 1, n) {
  if (rk[sa[i]] == rk[sa[i - 1]]) o_rk[sa[i]] = p;
  else o_rk[sa[i]] = ++p;
} copy(o_rk + 1, o_rk + 1 + n, rk + 1);
for (int len = 1; len < n; len <<= 1, m = n) {
  fill(cnt + 1, cnt + 1 + m, 0);
  copy(sa + 1, sa + 1 + n, id + 1);
  rep(i, 1, n) ++cnt[rk[id[i] + len]];
  rep(i, 1, m) cnt[i] += cnt[i - 1];
  per(i, n, 1) sa[cnt[rk[id[i] + len]]--] = id[i];
  copy(sa + 1, sa + 1 + n, id + 1);
  fill(cnt + 1, cnt + 1 + m, 0);
  rep(i, 1, n) ++cnt[rk[id[i]]];
  rep(i, 1, m) cnt[i] += cnt[i - 1];
  per(i, n, 1) sa[cnt[rk[id[i]]]--] = id[i];
  int p = 0;
  rep(i, 1, n) {
    if (rk[sa[i]] == rk[sa[i - 1]] && rk[sa[i] + len] == rk[sa[i - 1] + len]) o_rk[sa[i]] = p;
    else o_rk[sa[i]] = ++p;
  } copy(o_rk + 1, o_rk + 1 + n, rk + 1);
}
rep(i, 1, n) cout << sa[i] << ' ';

应用

• P4051 字符串加密

将 \(S\) 复制一遍并将副本放在后面得到 \(SS\)，对 \(SS\) 求一遍后缀数组即可。

• 判断字符串中是否出现某一子串

假设要在 \(S\) 中多次查找是否出现某一子串 \(T\)，观察到处理出来后缀数组后就有了字典序上的单调性，那么二分 \(sa\) 数组，每次比较某一后缀和 \(T\) 的大小关系即可，复杂度 \(O(|T| \log |S|)\)。

• 「USACO07DEC」Best Cow Line

处理出来原串的后缀数组和其反串的后缀数组，每次取时比较一下两个 \(rk\) 的大小即可。

\(height\) 数组

定义

假设 \(lcp(i, j)\) 表示字符串 \(\textrm{Suf}_S[i]\) 与 \(\textrm{Suf}_S[j]\) 的最长公共前缀。

\(height\) 的定义是：\(height[i] = lcp(sa[i], sa[i - 1])\)。特别地，\(height[1] = 0\)。

求法

引理：\(height[rk[i]] \ge height[rk[i - 1]] - 1\)。

证明：当 \(height[rk[i - 1]] \le 1\) 时式子显然成立；当 \(height[rk[i - 1]] > 1\) 时：
根据定义有 \(height[rk[i - 1]] = lcp(sa[rk[i - 1]], sa[rk[i - 1] - 1]) > 1 \Rightarrow lcp(i - 1, sa[rk[i - 1] - 1]) < 1\)。
假设用 \(aA\) 来表示最长公共前缀，则 \(\textrm{Suf}_S[i - 1]\) 表示为 \(aAX\)，\(\textrm{Suf}_S[sa[rk[i - 1] - 1]]\) 表示为 \(aAY\)。（\(X > Y\)，\(AX > AY\)，\(Y\) 可能是空串，\(X\) 不是空串）
可以得出 \(\textrm{Suf}_S[i] = AX\)，\(\textrm{Suf}_S[sa[rk[i - 1] - 1] + 1] = AY\)。（\(AX > AY\)）
又 \(\textrm{Suf}_S[sa[rk[i] - 1]]\) 且不存在后缀 \(Suf_S[k]\) 满足

\[\textrm{Suf}_S[sa[rk[i] - 1]] < \textrm{Suf}_S[k] < \textrm{Suf}_S[i] \]

故得到 \(AY \le \textrm{Suf}_S[sa[rk[i] - 1]] < AX\)，所以 \(\textrm{Suf}_S[sa[rk[i] - 1]]\) 与 \(\textrm{Suf}_S[i]\) 至少有公共前缀 \(A\)。
即 \(height[rk[i]] = lcp(i, sa[rk[i] - 1]) \ge |A|\) 又因为 \(|A| = height[rk[i - 1]] - 1\)，得到 \(height[rk[i]] \ge height[rk[i - 1]] - 1\)，证毕。

根据这个结论，就可以像 KMP 那样求 \(height\) 了。因为变化量是 \(O(n)\) 的，所以复杂度也是 \(O(n)\) 的。

code:

int k = 0;
rep(i, 1, n) {
  if (k) --k;
  while (s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
  height[rk[i]] = k;
}

应用

根据子串是后缀的前缀这个性质，\(height\) 数组可以处理许多子串问题。

• 两个子串的最长公共前缀

有定理 \(lcp(sa[i], sa[j]) = \min\limits_{k = i + 1}^j height[k]\)。很强的定理，但是不会证。OI-wiki 里面那篇关于后缀数组的文章格式有点抽象，所以没看。

基于这个定理，求子串 \(lcp\) 就变成了 RMQ 问题。

• 比较一个字符串的两子串大小

假设需要比较 \(X = S[l_1, r_1]\) 和 \(Y = S[l_2, r_2]\) 的关系。

• 若 \(lcp(l_1, l_2) \ge \min(|X|, |Y|)\)，那么 \(|X| < |Y| \Leftrightarrow X < Y\)。（其实这部分也可以用哈希做）

• 否则 \(X < Y \Leftrightarrow rk[l_1] < rk[l_2]\)。

• 本质不同子串数量

首先子串是后缀的前缀，所以大体是枚举后缀，再看有多少个后缀的前缀重复了。

考虑按照后缀排序的顺序来计算重复的前缀数量，因为有 \(lcp(sa[i], sa[j]) = \min height[i, \cdots, j]\)，所以后缀 \(\textrm{Suf}_S[sa[i]]\) 重复的前缀数是 \(height[i]\)。

故总计重复的前缀数就是 \(\sum\limits_{i = 1}^n height[i]\)，答案为 \(\frac{n(n + 1)}{2} - \sum\limits_{i = 1}^n height[i]\)。

• 是否有某字符串在文本串中至少不重叠地出现了两次

可以二分目标串的长度 \(|S|\) ，将 \(height\) 数组划分成若干个连续 \(\textrm{LCP}\) 大于等于 \(|S|\) 的段，利用 RMQ 对每个段求其中出现的数中最大和最小的下标，若这两个下标的距离满足条件，则一定有长度为 \(|S|\) 的字符串不重叠地出现了两次。

• 最长回文子串

求一个字符串中的最长回文子串。

可以用哈希做，枚举回文中心后二分并判断反串是否等于正串即可，\(O(n \log n)\)。

这里还有一个 SA 的做法。设当前字符串为 \(S\)，反串为 \(\hat{S}\)，将串 \(S\) 拼在 \(\hat{S}\) 后面，并用分隔符 | 分割，记新串为 \(S'\)。对新串求后缀数组后，在新串的正串部分中枚举回文中心 \(i\)，找到 \(S'\) 中反串部分该回文中心对应的点 \(j\)，那么该以 \(i\) 为回文中心形成的最长回文串为 \(lcp(i, j)\)，这样转化成了 RMQ 问题，复杂度 \(O(n \log n)\)。

• 重复次数最多的连续重复子串

一个字符串为连续重复子串当前仅当存在一个字符串重复若干次后得到该串。求一个字符串中重复次数最多的连续重复子串。

这种问题的基本方法是枚举长度并处理关键点。

考虑枚举重复子串的长度 \(L\)，接着每隔 \(L\) 个下标标记一个关键点，显然关键点下标是 \(1, L + 1, 2L + 1, 3L + 1, \cdots\)。可以发现重复次数等于子串里关键点数量。对于只包含 \(1\) 个的作特殊处理；考虑一个连续重复子串包含至少 \(2\) 个关键点的情况，对其中相邻的两个关键点求出其前缀的 \(lcs\)（最长公共后缀）和后缀的 \(lcp\) 并相应地计算即可。复杂度 \(O(n \log n)\)。

• 最长公共子串

求两个字符串的最长公共子串。

这种两个字符串的方法是将一个放在另一个后面并用分隔符隔开，接着对新串用后缀数组。

假设是字符串 \(A\) 和 \(B\)，并拼接出串 \(A|B\)（中间的 \(|\) 是分割符），处理出新串的 \(height\) 后，枚举相邻的两个 \(sa\) 并特判是否在同一子串中即可。

• 不可重最长重复子串

求一个字符串中最长的重复了两遍的子串，且出现的位置不能重叠。

主要思想是对 \(height\) 的大小进行分组，这个思想也将在后面用到。

先二分答案，题目转化成：判定是否存在两个长度为 \(k\) 个不相交的相同子串。将 \(height\) 数组分组，分组后使每组相邻的两个后缀的 \(lcp \ge k\)。如，字符串为 \(aabaaaab\) 且 \(k = 2\) 时，有：

这样分组后，会有几个性质：

1. 每组的字符串两两之间的 \(\textrm{LCP}\) 长度 \(\ge k\)。
2. 对于同一组，字符串两两之间的 \(\textrm{LCP}\) 的长度为 \(k\) 的前缀都相同。
3. 对于两个不同的组，字符串的 \(\textrm{LCP}\) 对应的长度为 \(k\) 的前缀不同。

根据这些性质，对于某组，只需判定是否存在两个在这组的不相交的子串即可。

• 出现在至少 \(k\) 个字符串中的最长子串

有 \(n\) 个字符串，查找出现在至少 \(k\) 个字符串中的最长子串。

结合 最长公共子串 和 不可重最长重复子串 的方法，先将这 \(n\) 个字符串连接起来，用分隔符分开，并求出其后缀数组与 \(height\)。再二分答案，将 \(height\) 分组，接着判断每组是否能拆成 \(k\) 个即可。复杂度 \(O(n\log n)\)。