只会倍增

简介

前置知识：基数排序

$O(n)$，通过离散化，前缀和可求出字符串的排名（如果要稳定的话，记得从后往前枚举）。

算法目的

在 $O(n \log n)$ 的时间里，将所有的后缀按字典序排序。
$sa[i]$：排名第 $i$ 位的是第几个后缀。
$rk[i]$：第 $i$ 个后缀的排名是多少。
$height[i]$：$sa[i]$ 和 $sa[i - 1]$ 的最长公共前缀的长度。

实现

我们从前往后处理，假设我们已经将序列的前 $k$ 个字符作为第一关键字排好了序，根据倍增思想，我们下一步就应该将前 $2k$ 个字符作为第一关键字排序。那该如何实现呢？可以发现，我们可以先将后 $k$ 个字符作为第一关键字排序，再将前 $k$ 个字符作为第一关键字排序即可。
$sa_i$ 已经求出来了，那 $height_i$ 呢？
其实关于 $height_i$ 我们有一个定理，对于 $lcp(i,j)$ 恒等于 $\min(lcp(i,k), lcp(k, j)),i \le k \le j$ 这个用夹逼法（~~作者也一脸懵，还请读者自行证明~~）

例题：Acwing2715. 后缀数组

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, m;
char s[N];
int sa[N], x[N], y[N], c[N], rk[N], height[N];
void get_sa()
{
	for(int i = 1;i <= n;i ++) c[x[i] = s[i]] ++;
	for(int i = 2;i <= m;i ++) c[i] += c[i - 1];
	for(int i = n; i;i --) sa[c[x[i]] --] = i;
	for(int k = 1;k <= n;k <<= 1)
	{
		int num = 0;
		for(int i = n - k + 1;i <= n;i ++) y[ ++ num] = i;
		for(int i = 1;i <= n;i ++)
		{
			if(sa[i] > k)
				y[++ num] = sa[i] - k;
		}
		for(int i = 1;i <= m;i ++) c[i] = 0;
		for(int i = 1;i <= n;i ++) c[x[i]] ++;
		for(int i = 2;i <= m;i ++) c[i] += c[i - 1];
		for(int i = n; i;i --) sa[c[x[y[i]]] --] = y[i], y[i] = 0;
		swap(x, y);
		x[sa[1]] = 1, num = 1;
		for(int i = 2;i <= n;i ++)
			x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++ num;
		if(num == n) break;
		m = num;
	}
}
void get_height()
{
	for(int i = 1;i <= n;i ++) rk[sa[i]] = i;
	for(int i = 1, k = 0;i <= n;i ++)
	{
		if(rk[i] == 1) continue;
		if(k) k --;
		int j = sa[rk[i] - 1];
		while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) k ++;
		height[rk[i]] = k;
	}
}
int main()
{
	scanf("%s", s + 1);
	n = strlen(s + 1), m = 122;
	get_sa();
	get_height();
	for(int i = 1;i <= n;i ++) printf("%d ", sa[i]);
	puts("");
	for(int i = 1;i <= n;i ++) printf("%d ", height[i]);
	return 0;
}