后缀数组（Suffix Array）

是什么？

后缀数组 $sa_i$ 的意义是，字典序第 $i$ 小的后缀编号。这里，令一个后缀的编号为它开始的位置。

还有一个重要的辅助数组 $rk_i$，代表编号为 $i$ 的后缀排名。

显然，有性质 $sa_{rk_i} = rk_{sa_i} = i$。

比如，字符串 ababa 的五个后缀分别为 ababa，baba，aba，ba，a，排序后为 a，aba，ababa，ba，baba，所以 $sa = [5, 3, 1, 4, 2], rk = [3, 5, 2, 4, 1]$。

我们的目标就是对于一个字符串，求出它的后缀数组。

下文设其长度为 $n$，下标从 $1$ 开始。

$O(n^2 \log n)$

我们考虑 sort，其中比较两个后缀直接暴力比较。其中 sort 的时间复杂度是 $O(n \log n)$，比较的时间复杂度是 $O(n)$，总时间复杂度为 $O(n^2 \log n)$。

$O(n \log^2 n)$

做法一

我们考虑优化刚刚的比较过程。发现，比较两个字符串可以用二分 + hash 找到第一个不相同的位置，并比较该位置的值，时间复杂度 $O(\log n)$。我们只需要提前预处理整个串的哈希即可，总时间复杂度变为 $O(n \log^2 n)$。

因为该做法不能进一步优化，所以并没有放代码。

做法二

考虑倍增。倍增过程如下：

• 先令当前长度 $k$ 为 $1$，并 sort 求出每个长度为 $1$ 的子串（即单个字符）排名 $rk'_{1, i}$。

• 用两个长度为 $k$ 的子串的排名，即 $rk'_{k, i}, rk'_{k, i + k}$，为 sort 的第一第二关键字，就可以对字符串的每个长度为 $2k$ 的子串进行排序，得到 $sa'_{2k, i}, rk'_{2k, i}$，并令 $k \gets 2k$。

• 重复该过程直到 $k \ge n$，最终的 $sa, rk$ 就是 $sa'_k, rk'_k$。

倍增会重复 $O(\log n)$ 次，单次时间复杂度 $O(n \log n)$，总时间复杂度为 $O(n \log^2 n)$。

模板题代码：

#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;
const int N = 1000001;
struct pii{int a, b, id;
	inline bool operator<(pii x)const{return a == x.a ? b < x.b : a < x.a;}
	inline bool operator!=(pii x){return a != x.a || b != x.b;}
}srt[N << 1]; // 排序结构体
int n, sa[N << 1], rk[N << 1]; // 这里数组应开两倍防止访问越界
char s[N];
int main(){
	scanf("%s", s + 1), n = strlen(s + 1);
	for (int i = 1;i <= n;i ++) srt[i] = {s[i], 0, i};
	sort(srt + 1, srt + n + 1);
	for (int i = 1;i <= n;i ++) sa[i] = srt[i].id;
	for (int i = 1, c = 0;i <= n;i ++) c += srt[i] != srt[i - 1], rk[srt[i].id] = c;
	// 这里相同的段应赋相同的 rk
	for (int b = 1;b < n;b <<= 1){
		for (int i = 1;i <= n;i ++) srt[i] = {rk[i], rk[i + b], i};
		sort(srt + 1, srt + n + 1);
		for (int i = 1;i <= n;i ++) sa[i] = srt[i].id;
		for (int i = 1, c = 0;i <= n;i ++) c += srt[i] != srt[i - 1], rk[srt[i].id] = c;
		// 同上
		if (rk[sa[n]] >= n) break; // 小优化
	}
	for (int i = 1;i <= n;i ++) printf("%d ", sa[i]);
}

$O(n \log n)$

不难发现，$rk$ 的值域是 $1 \sim n$，而且排序是个简单的双关键字排序，所以可以用桶排替代 sort。

这样就把单次时间复杂度降到了 $O(n)$，总时间复杂度为 $O(n \log n)$。

代码：

#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 1000001;
int n, rk[N << 1], sa[N << 1], _rk[N << 1], _sa[N << 1], cnt[N];char ch[N];
// 数组开两倍，原因同上
int main(){
	scanf("%s", ch + 1), n = strlen(ch + 1);int m = 127;
	for (int i = 1;i <= n;i ++) cnt[rk[i] = ch[i]] ++;
	for (int i = 1;i <= m;i ++) cnt[i] += cnt[i - 1];
	for (int i = n;i >= 1;i --) sa[cnt[rk[i]] --] = i;
	memset(cnt, 0, m + 1 << 2), m = 0;
	memcpy(_rk, rk, n + 1 << 2); // 复制备用
	for (int i = 1;i <= n;i ++){
		if (_rk[sa[i]] == _rk[sa[i - 1]]) rk[sa[i]] = m;
		else rk[sa[i]] = ++ m;
	}// 这里相同的段也应赋相同的 rk
	for (int k = 1;k < n;k <<= 1){
		memcpy(_sa, sa, n + 1 << 2);
		for (int i = 1;i <= n;i ++) cnt[rk[_sa[i] + k]] ++;
		for (int i = 1;i <= m;i ++) cnt[i] += cnt[i - 1];
		for (int i = n;i >= 1;i --) sa[cnt[rk[_sa[i] + k]] --] = _sa[i];
		// 对第二关键字 rk[i + k] 基数排序，相同的顺序不变
		memset(cnt, 0, m + 1 << 2);
		memcpy(_sa, sa, n + 1 << 2);
		for (int i = 1;i <= n;i ++) cnt[rk[_sa[i]]] ++;
		for (int i = 1;i <= m;i ++) cnt[i] += cnt[i - 1];
		for (int i = n;i >= 1;i --) sa[cnt[rk[_sa[i]]] --] = _sa[i];
		// 对第一关键字 rk[i] 基数排序
		memset(cnt, 0, m + 1 << 2), m = 0;
		memcpy(_rk, rk, n + 1 << 2);
		for (int i = 1;i <= n;i ++) {
			if (_rk[sa[i]] == _rk[sa[i - 1]] && _rk[sa[i] + k] == _rk[sa[i - 1] + k]) rk[sa[i]] = m;
			else rk[sa[i]] = ++ m;
		} // 同上
		if (m == n) break; // 小优化
	}
    for (int i = 1;i <= n;i ++) printf("%d ", sa[i]);
}

height 数组

我们定义 height 数组 $h_i = \operatorname{lcp}(sa_{i - 1}, sa_i)$，这里 $\operatorname{lcp}(i, j)$ 是后缀 $i$ 与后缀 $j$ 的最长前缀，特殊的，$h_1 = 0$。

一个结论

$\operatorname{lcp}(sa_i, sa_j) = \min_{k = i + 1}^j h_k$。

这个比较简单，感性理解即可。

一个引理

$h_{rk_i} \ge h_{rk_{i - 1}} - 1$。

证明

根据 $h$ 的定义，可以直接得出 $\operatorname{lcp}(sa_{rk_i - 1}, i) \ge \operatorname{lcp}(sa_{rk_{i - 1} - 1}, i - 1) - 1$。然后我们考虑反证法，证明 $\operatorname{lcp}(sa_{rk_i - 1}, i) < \operatorname{lcp}(sa_{rk_{i - 1} - 1}, i - 1) - 1$ 非法。把这些后缀都画出来：

其中 X 代表失配，$ch$ 是单个字符，相同的字母表示相同的段。$D$ 则是 $\operatorname{lcp}(sa_{rk_{i - 1} - 1} + 1, i)$（即 $\operatorname{lcp}(sa_{rk_{i - 1} - 1}, i - 1) - 1$） 比 $\operatorname{lcp}(sa_{rk_i - 1}, i)$ 多出来的部分，它是 $B$ 的一个非空前缀。

因为 $sa_{rk_{i - 1} - 1}$ 的字典序比 $i - 1$ 的小，所以 $sa_{rk_{i - 1} - 1} + 1$ 的字典序比 $i$ 的小（同时去掉一个相同字符）。然后根据上面的结论，$sa_{rk_i - 1}$ 比 $sa_{rk_{i - 1} - 1} + 1$ 和 $i$ 在字典序上更接近，所以 $\operatorname{lcp}(sa_{rk_i - 1}, i) \ge \operatorname{lcp}(sa_{rk_{i - 1} - 1} + 1, i) = \operatorname{lcp}(sa_{rk_{i - 1} - 1}, i - 1) - 1$，这就产生了矛盾，所以结论成立。

$O(n)$ 求

直接用刚刚的引理暴力求即可。

for (int i = 1, j = 0;i <= n;i ++){
	if (j) j --;
	while (s[i + j] == s[sa[rk[i] - 1] + j]) j ++;
	h[rk[i]] = j;
}

因为 $k$ 不会超过 $n$，而且最多减 $n$ 次，所以最多加 $2n$ 次，总复杂度是 $O(n)$。

不同子串个数

我们知道，子串就是后缀的前缀。所以答案就是，所有的子串个数减去重复个数。我们考虑按照字典序顺序加入后缀，每次加入的新后缀和上一个后缀的重复前缀，一定包含与其他后缀的重复前缀。而这个重复前缀的个数恰好就是 $h_i$ 个，所以总共的答案是 $\frac {n(n - 1)}2 \sum_{i = 1}^n h_i$。