「Note」后缀数组

上课直接听晕过去。。。

$\mathbb{Problem}$

给定一个字符串，要求对其所有的后缀进行排序。
朴素做法直接是按字典序写一个 cmp 函数，但是两两之间比较的复杂度会飙升到 $\Theta(n)$，sort 一遍下来是 $\Theta(n ^ 2 log_2^n)$ 的时间复杂度，显然不够优，此时可以引进 后缀数组 求解。

$\mathbb{Definitions}$

后缀数组 $\mathtt{Suffix Array}$ 由两个主要的数组组成。一个是 后缀编号 $\mathtt{sa}$ ，一个是 数组排名 $\mathtt{rnk}$。

其实是顾名思义， $\mathtt{sa_i}$ 表示 排名为 $i$ 的后缀的编号， $\mathtt{rnk_i}$ 表示 编号为 $i$ 的后缀的排名。
表示可能和课上略有所出入，最终目的是便于理解。

$\mathbb{Build}$

思想和 基数排序 类似。
如果不会基排，其实也无所谓。

既然提到 基数排序 和 上面的 朴素做法， 那么可以考虑对于 $\Theta(n ^ 2 log_2^n)$ 的算法进行优化。

这里直接给出做法。

当时上课时看到就傻了，这个倍增是个什么鬼哟？ 其实 ppt 上有一句

利用上一轮比较的结果

也不难想到对于后缀 $[i, n]$ 的长度为 $len$ 的前缀实际上相当于 后缀 $[i + 2, n]$ 的长度为 $\frac{len}{2}$ 的前缀 拼上 后缀 $[i + 4, n]$ 的长度为 $\frac{len}{2}$ 的前缀。

而这两个前缀的信息已经在上一层处理过，那么可以直接拿来用。

说着确实很玄，放一张 oi-wiki 上的图应该就很清晰了。

$\mathbb{Code}$

int n, m, w[MAXN], sa[MAXN], now[MAXN], rnk[MAXN], tmp[MAXN];
char s[MAXN];
// w[i] 记录当前排名为 <= i 的后缀个数, now 和 tmp 是 未成形的 sa 和 rnk

void init(int n, int m) { // n 是 |string|, m 是字符集大小
	// w[i] 记录当前排名为 <= i 的后缀个数，所有最后来了一边前缀和
	for (int i = 1; i <= m; i++) w[i] = 0;
	for (int i = 1; i <= n; i++) w[rnk[i]]++;
	for (int i = 2; i <= m; i++) w[i] += w[i - 1];
}

// 功能是排序装桶（对于当前）
void push_in(int n) { for (int i = n; i >= 1; i--) sa[w[rnk[now[i]]]--] = now[i]; }

void Sa(int n, int m) {

	for (int i = 1; i <= n; i++) rnk[i] = s[i], now[i] = i; // 进行第一次单字符排序
	init(n, m), push_in(n);

	for (int len = 1; len < n; len <<= 1) { // 当前比较长度为 len * 2

		int pos = 0; init(n, m); // 每次要重新计算桶的大小
		for (int i = n - len + 1; i <= n; i++) now[++pos] = i; // 如果倍增后 len + i 爆出去了，相当于低位补空，直接排在前面
		for (int i = 1; i <= n; i++) if (sa[i] > len) now[++pos] = sa[i] - len; // 拼 计算 now
		push_in(n), memcpy(tmp, rnk, sizeof(rnk)), pos = 0;
		for (int i = 1; i <= n; i++) {
			if (tmp[sa[i]] != tmp[sa[i - 1]] || tmp[sa[i] + len] != tmp[sa[i - 1] + len]) pos++; // 拼
			rnk[sa[i]] = pos; // 标记排名
		}
		m = pos; // 重新分配桶的空间

	}

}