虽然这是基础算法，但我已经好几次忘记它怎么写了，反倒是 SAM 记得很牢。
为了避免比赛中因这个爆蛋，我打算仔细梳理一下它的原理。
问题：给你一个字符串，你需要求出 \(sa_i,rk_i\)，其中 \(sa_i\) 表示排名为 \(i\) 的后缀，\(rk_i\) 表示后缀 \(i\) 的排名。
首先暴力就是直接快排，里面二分哈希，\(\Theta(n \log^2 n)\)。
然后考虑倍增。
每次我们按照后缀的前 \(w\) 个字符排序，然后 \(w\) 每次乘 \(2\)，最后就能完成排序。
最初 \(w=1\)，若串为 \(\verb!ababa!\)，则排序结果如下：
接着我们令 \(w=2\)，考虑求出此时每个后缀的排名。
不难发现，此时后缀的排名就是以它自己的排名为第一关键字，它后面的那个后缀为第二关键字排序后的排名，也就是 \(\verb!pair!\) \((rk_i,rk_{i+1})\) 的排名。
同理，\(w\) 的排序结果转移到 \(2 \times w\) 就是按照 \(\verb!pair!\) \((rk_i,rk_{i+w})\) 排序。
此时直接暴力排序依然是 \(\Theta(n \log^2 n)\) 的。
考虑基数排序优化，可以得到 \(\Theta(n \log n)\) 的复杂度。
代码：
inline void kun_sort(){
rep(i,0,m) sm[i]=0;
rep(i,1,n) ++sm[rk[i]];
rep(i,1,m) sm[i]+=sm[i-1];
//处理第一关键字排名，现在 sm[i] 表示的是第一关键字为 rk[i] 的最后排名
per(i,n,1) sa[sm[rk[tp[i]]]--]=tp[i];
//倒序加入
}
inline void SA(){
rep(i,1,n) tp[i]=i,rk[i]=s[i];
m=200,kun_sort();
int tot=0;
for (int w=1;tot<n;w<<=1){
tot=0;
rep(i,n-w+1,n) tp[++tot]=i;
rep(i,1,n) if (sa[i]>w) tp[++tot]=sa[i]-w;
//按第二关键字排序
kun_sort(),swap(tp,rk);
tot=rk[sa[1]]=1;
rep(i,2,n)
rk[sa[i]]=(tp[sa[i]]==tp[sa[i-1]] && tp[sa[i]+w]==tp[sa[i-1]+w])?tot:++tot;
m=tot;
}
}
\(\rm height\) 数组表示 \(sa_i\) 和 \(sa_{i-1}\) 的 LCP。
基于下面这个结论，我们可以快速求出 \(\rm height\) 数组：
\[height_{rk_i} \ge height_{rk_{i-1}}-1 \]int k=0;
rep(i,1,n){
if (k) --k;
while (i+k<=n && sa[rk[i-1]]+k<=n && s[i+k]==s[sa[rk[i-1]]+k]) ++k;
height[rk[i]]=k;
}