1. 后缀数组

1.1 内容

我们将一个字符串 \(s\) 的所有后缀按照字典序从小到大排序得到数组 \(sa\)，其中 \(sa_i\) 表示以 \(sa_i\) 开始的后缀排名是第 \(i\) 个。

这个数组就叫后缀数组（Suffix Array, SA）。考虑到长度各不相同，所以显然是个排列，设数组 \(rk\) 是这个数组的逆排列。

我们考虑倍增：先对所有长为 \(2^w\) 的子串排序，然后对于 \(2^{w+1}\) 的子串可以表示为一个二元组 \((rk_i, rk_{i+2^w})\)，按照这个数组排序就是 \(2^{w+1}\) 的子串的排序。

直接快排是 \(O(n \log^2 n)\)，我们考虑优化掉快排，注意到值域不大，考虑基数排序。

我们先对第二关键字排序，再对第一关键字排序，由于桶排是稳定排序，这样排就能排出来。

还有一个小优化，如果排序到某一步就各不相同了可以直接结束。

下面是模板题代码，参考了 qAlex_Weiq 的实现：

#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6 + 5;

char s[N];
int n, sa[N] = {0}, rk[N] = {0}, buc[N] = {0}, ork[N] = {0}, id[N] = {0};

void SA() {
	int m = (1 << 7), p = 0;
	for (int i = 1; i <= n; i++)
		buc[rk[i] = s[i]]++;
	for (int i = 1; i <= m; i++)
		buc[i] += buc[i - 1];
	for (int i = n; i >= 1; i--)
		sa[buc[rk[i]]--] = i;
	for (int w = 1; ; m = p, p = 0, w <<= 1) {
		for (int i = n - w + 1; i <= n; i++) id[++p] = i;
		for (int i = 1; i <= n; i++) if (sa[i] > w) id[++p] = sa[i] - w;
		p = 0;
		for (int i = 1; i <= m; i++) buc[i] = 0;
		for (int i = 1; i <= n; i++) buc[ork[i] = rk[i]]++;
		for (int i = 1; i <= m; i++) buc[i] += buc[i - 1];
		for (int i = n; i >= 1; i--) sa[buc[rk[id[i]]]--] = id[i];
		for (int i = 1; i <= n; i++) rk[sa[i]] = (ork[sa[i - 1]] == ork[sa[i]] && ork[sa[i - 1] + w] == ork[sa[i] + w]) ? p : ++p;
		if (p == n)
			break;
	}
}

int main() {
	scanf("%s", s + 1);
	n = strlen(s + 1);
	SA();
	for (int i = 1; i <= n; i++)
		printf("%d ", sa[i]);
	return 0;
}

1.2 height 数组

SA 能解决一个很重要的问题：任意两个子串的 LCP，而这就基于 height 数组。

定义 \(height_i\) 表示 \(sa_{i-1}\) 与 \(sa_{i}\) 的 LCP 长度，再定义 \(h_i\) 表示 \(height_{rk_i}\)。我们有一条重要结论：

这就意味着我们可以类似 KMP 的方法来求出这个 \(height\) 数组，时间复杂度 \(O(n)\)。

注意需要设置边界字符。

s[0] = s[n + 1] = '#';
for (int i = 1, k = 0; i <= n; i++) {
	if (k)
		k--;
	while (s[i + k] == s[sa[rk[i] - 1] + k])
		k++;
	ht[rk[i]] = k;
}

1.3 应用

求任意两个子串的 LCP 长度

我们有一个很重要的结论：\(x,y\) 开始的后缀的 LCP 长度等于 \([rk_x, rk_y]\) 的区间中 \(height\) 的最小值，这个结论不难证明。

将子串转化成后缀不影响，变成了 RMQ 问题，一般用 ST 表进行查询。

P2408 不同子串个数

考虑到每个子串都是前缀的后缀，所以我们可以枚举所有后缀。

我们考虑逐步计数，我们从 \(sa_1\) 开始计数，我们发现，\(sa_2\) 新增的子串个数刚好等于 \(|s[sa_2, n]| - height_{2}\)，而后面的也是一样的。

所以最终我们就得到答案为 \(\frac{n(n+1)}{2} - \sum_i height_i\)。

提交记录

P5546 [POI2000] 公共串

首先对于多串问题，必须把他们都接在一起用特殊字符隔开，然后再跑 SA。

我们考虑二分，然后我们将所有 \(height < d\) 的断开，分成若干段，则如果有一段的的后缀中包括了 \(n\) 种字符串的就是可行的。

显然我们可以用双指针或者排序后并查集合并去掉二分。

提交记录

P4248 [AHOI2013] 差异

将和式拆开，真正难算的是两两的 LCP 之和。

我们转化成求所有区间的最小值之和，这个问题可以用单调栈来做。

我们定义最小值是最靠左的那个，这样最小值就唯一了，然后处理出他作为最小值最远的左右段点，然后直接计算总共有多少个区间即可，时间复杂度 \(O(n)\)。

提交记录

P3181 [HAOI2016] 找相同字符

我们还是将两个串接到一起求 SA。

然后我们发现答案实际上就是两两属于不同字符串的后缀的 LCP 之和，我们可以容斥，用总的减去两个分别的，就是上面的问题。

提交记录

CF123D String

第一种是将其转化成两两的 LCP，但是这是因为这道题式子本身的特性。

还有一种可以对于任意的式子都能解决。

我们还是枚举最小值和所处区间，我们发现，这意味着这个最小值就去出现了这个区间的长度次，并且所有比这个区间左右两边小于最小值的还大的一直到最小值都是如此，我们可以直接统计这些子串的贡献。

但是这样就漏到了那些只出现一次的，所以我们还要用总的减去两侧 \(\height\) 的最大值，也就是那些不会被统计到的贡献。

时间复杂度还是 \(O(n)\)。

提交记录

P2178 [NOI2015] 品酒大会

我们考虑之前讲过的哪种倒过来用并查集不断合并统计贡献的。

显然两个后缀的贡献会在所有小于等于其 LCP 的时候被统计到，我们用并查集维护，合并时更新答案即可。

提交记录