SA 的定义
一个字符串有 \(n\) 个后缀，把 \(n\) 个后缀按字典序排序，得到数组 \(sa\)。\(sa\) 的每一个元素是每个后缀的第一个字符的 index。
\(rk\) 数组代表了原先的每个后缀在排序后的位置。
例如：eaabd，其后缀为 eaabd aabd abd bd d，排序后为 aabd abd bd d eaabd，\(sa = \{2,3,4,5,1\}, rk = \{5,1,2,3,4\}\)。
SA 怎么求
考虑倍增。
初始轮，\(w=1\)，把 \(sa\) 按每个字符排序。
接下来的每一轮，\(w \leftarrow w \times 2\)，这次的串 \(x\) 应该由上一轮的 \([x,x+w)\) 和 \([x+w,x+2w)\) 两个串拼成。把 \(sa\) 以 \(rk_x\) 为第一关键字，\(rk_{x+w}\) 为第二关键字排序，其中 \(rk\) 为由上一轮的排序的 \(sa\) 得到的 \(rk\)。
时间复杂度 \(O(n \log^2 n)\)，如果用基数排序可以做到 \(O(n \log n)\)。
int sa[MAXN], rk[MAXN * 2], tmp[MAXN * 2];
// 因为有 +w，开大一倍防止越界
// 因为在统计这一轮的 rk 时还要用到上一轮的 rk，所以这一轮的 rk 先放在 tmp 里，结束后 copy
void build_SA(string S) {
rep(i, 1, n)
sa[i] = i, rk[i] = S[i];
for (int w = 1; w <= n; w <<= 1) {
auto cmp = [&](int x, int y) -> bool {
if (rk[x] == rk[y])
return rk[x+w] < rk[y+w];
return rk[x] < rk[y];
};
sort(sa+1, sa+n+1, cmp);
rep(i, 1, n)
tmp[sa[i]] = tmp[sa[i-1]] + cmp(sa[i-1], sa[i]);
copy(tmp+1, tmp+n+1, rk+1);
}
}
SA 其实还有 \(O(n)\) 求法，但是并不实用。
例 1：\(k\) 小表示法
例：P4051 [JSOI2007] 字符加密 给定一个字符串 \(S\)，仿照最小表示法问题，求其 \(k\) 小表示法。
解：对 \(S + S\) 求 SA 即可。时间复杂度 \(O(n \log^2 n)\)。
Height 数组
定义：\(h_i = \text{LCP}(sa_i, sa_{i-1})\)。特别地，\(h_1 = 0\)。求出 \(h\)。
可以证明：\(h[rk_i] \ge h[rk_{i-1}] - 1\)。
基于这个引理，我们按 \(rk\) 顺序暴力求出 \(h\)，均摊后总复杂度就是 \(O(n)\)。
int k = 0;
rep(i, 1, n) {
int j = sa[rk[i] - 1];
if (k) k--;
while (S[i + k] == S[j + k])
k++;
h[rk[i]] = k;
}
例 2：本质不同子串数量
对于每一个相同子串，我们都只在它出现的最大后缀中记录它的贡献。
对于每个后缀 \(i\)，出现在 \(sa[rk_i + 1]\) 中的前缀不会被记录贡献，而没有出现的则会记录贡献，没被记录贡献的子串数为 \(h[rk_i + 1]\)。
因此，答案为 \(\frac {n (n+1)} 2 - \sum\limits_{i=2}^n h_i\)。不开 long long 见祖宗