倍增求后缀数组
1. 一些定义
后缀 \(i\)：子串 \([\text{len}(S)-i+1,\text{len}(S)]\)；
\(\text{SA}(i)\)：排名为 \(i\) 的后缀；
\(\text{rank}(i)\)：后缀 \(i\) 的排名，\(\forall i>n,\text{rank}(i)=0\)。
后缀数组即 \(\text{SA}\)。
2. 求法
先对每个单独的字符从小到大排序，得到每个字符的排名和后缀数组，记排名为 \(\text{rank}_1\)
再把 \(i\) 和 \(i+1\) 拼在一起，得到长度为 \(2\) 的串再排序。
以 \(\text{rank}_1(i)\) 为第一关键字，\(\text{rank}_1(i+1)\) 为第二关键字从小到大排序。
这样可以得到每个长度为 \(2\) 的串的排名和后缀数组，记排名为 \(\text{rank}_2\)
再把 \(i\) 和 \(i+2\) 拼在一起，得到长度为 \(4\) 的串再排序。
以 \(\text{rank}_2(i)\) 为第一关键字，\(\text{rank}_2(i+2)\) 为第二关键字从小到大排序。
这样可以得到每个长度为 \(4\) 的串的排名和后缀数组，记排名为 \(\text{rank}_4\)。
以此类推，对于长度 \(w\)，将 \(i\) 和 \(i+w\) 拼在一起，得到长度为 \(2w\) 的串再排序。
以 \(\text{rank}_{w}(i)\) 为第一关键字，\(\text{rank}_w(i+w)\) 为第二关键字从小到大排序。
这样可以得到每个长度为 \(2w\) 的串的排名和后缀数组，记排名为 \(\text{rank}_{2w}\)。
一直倍增直到 \(w > n\) 即可，时间复杂度：\(O(n\log^2n)\)。
这样时间复杂度的瓶颈在于 \(O(n\log n)\) 的排序。
考虑到排名的值域为 \(O(n)\)，可以使用基数排序优化至 \(O(n)\)。
这样总时间复杂度就为 \(O(n\log n)\)。
3. 基数排序
对于有 \(k\) 个关键字的排序，我们从第 \(k\) 个关键字枚举到第 \(1\) 个关键字，
每次对当前关键字做一次稳定的排序，便可完成整个排序。
一般选组计数排序作为【稳定的排序】，时间复杂度：\(O((n+w)k)\)。
这样为什么是对的呢？
对于第 \(i\) 个关键字，\([i+1,k]\) 的关键字都已排好。
由于第 \(i\) 个关键字的优先级更高，如果第 \(i\) 个关键字不等，直接按第 \(i\) 个排即可。
如果第 \(i\) 个关键字相等，由于计数排序为稳定的排序，相同元素的顺序不会改变，仍为 \([i+1,k]\) 关键字的排序结果。
4. 实现细节
在倍增时，可能会出现相同的字符串，这时它们的排名必须相等。
所以处理排名时还需要一个去重操作。
还有一个优化，如果某次处理时已经没有重复的字符串，
那最终排名和后缀数组都已确定，结束整个算法就行，实测优化很大。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, sa[N], rk[N << 1]; // 避免 i + w 越界
char S[N];
struct node {int key[2], id;};
node a[N], b[N];
int cnt[N];
void sort(int p, int w) { // 计数排序
memset(cnt, 0, sizeof(cnt));
for (int i = 1; i <= n; i ++) cnt[a[i].key[p]] ++;
for (int i = 1; i <= w; i ++) cnt[i] += cnt[i - 1];
for (int i = n; i >= 1; i --) b[cnt[a[i].key[p]] --] = a[i];
for (int i = 1; i <= n; i ++) a[i] = b[i];
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> (S + 1);
n = strlen(S + 1);
for (int i = 1; i <= n; i ++) rk[i] = S[i]; // 第一遍排序
for (int w = 1; w <= n; w <<= 1) {
int maxw = 0;
for (int i = 1; i <= n; i ++) // i 为第一关键字, i + w 为第二关键字
a[i] = {{rk[i], rk[i + w]}, i},
maxw = max(maxw, rk[i]);
sort(1, maxw); sort(0, maxw); // 第二关键字先排序, 第一关键字后排序
int p = 0;
for (int i = 1; i <= n; i ++) {
if (a[i].key[0] == a[i - 1].key[0] // 去重操作
&& a[i].key[1] == a[i - 1].key[1]) rk[a[i].id] = p;
else rk[a[i].id] = ++ p;
sa[i] = a[i].id; // 统计后缀数组
}
if (p == n) break; // 没有重复字符串, 优化
}
for (int i = 1; i <= n; i ++) cout << sa[i] << " ";
return 0;
}