前言
去年省选前就想搞的东西，也算是在省选前搞完了。（雾）
后缀数组
基本定义
后文中使用“后缀 \(i\)”指代 \(S[i:n]\)，\(n\) 为 \(|S|\)。
\(sa_i\) 表示字典序第 \(i\) 小的后缀，\(rk_i\) 表示后缀 \(i\) 的字典序排名。二者显然互逆。
实现
\(O(n\log^2 n)\)
倍增思想。首先对原串所有长度为 \(1\) 的子串按字典序排序得到 \(sa,rk\)，然后倍增长度 \(w\)。
当处理到 \(|S|=2w\) 的子串时，我们已经拥有了 \(|S|=w\) 的所有子串的 \(sa,rk\) 信息。考虑将每个 \(|S|=2w\) 的子串分为前后两个 \(|S'|=w\) 的子串（不够的留空，空字符字典序最小），这样每个串就有了第一第二两个关键字，同时所有关键字之间的相对大小关系是已知的。我们直接 \(O(n\log n)\) 地 sort 一遍即可。sort 之后根据得到的 \(sa\) 得到新的 \(rk\) 数组，记得去重。
因为只会跑 \(\log n\) 次，故而复杂度 \(O(n\log^2 n)\)。
\(O(n\log n)\)
沿用两只老哥的做法，发现复杂度瓶颈在于每次 sort 的复杂度。考虑到要排序的值域在 \(O(n)\) 级别，考虑使用基数排序，同时去重容易 \(O(n)\) 实现，于是单轮复杂度降到 \(O(n)\)，复杂度 \(O(n\log n)\)。基排是稳定排序，由于我们是 cnt-- 倒着得到位置，所以只需按第二关键字倒序枚举填入即可完成排序。
但这样常数太大了，考虑优化。注意到对第二关键字的排序实际无需搞基排，因为原 \(sa\) 数组实际上已经给所有第二关键字排好序了，我们只需要将所有第二关键字为空字符的节点挪到 \(sa\) 数组最前面即可。
另一个小优化是每次将值域更新为 \(rk\) 去重后的大小，当值域为 \(n\) 时整个数组已经有序了可以直接结束。
int sa[N],rk[N],cnt[N],id[N],ok[N];
void SA(string s){int n=s.size(),m=127;s=' '+s;rep(i,1,n)++cnt[rk[i]=s[i]];rep(i,1,m)cnt[i]+=cnt[i-1];rep(i,1,n)sa[cnt[rk[i]]--]=i;for(int w=1;w==1||m<n;w<<=1){int cur=0;rep(i,n-w+1,n)id[++cur]=i;rep(i,1,n)if(sa[i]>w)id[++cur]=sa[i]-w;rep(i,1,m)cnt[i]=0;rep(i,1,n)++cnt[rk[i]];rep(i,1,m)cnt[i]+=cnt[i-1];per(i,n,1)sa[cnt[rk[id[i]]]--]=id[i];m=0;rep(i,1,n)ok[i]=rk[i];rep(i,1,n){if(ok[sa[i]]!=ok[sa[i-1]]||sa[i]>n-w||sa[i-1]>n-w||ok[sa[i]+w]!=ok[sa[i-1]+w])++m;rk[sa[i]]=m;}}
}