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)$。

虽然但是这题哈希好像也是 2log

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：本质不同子串数量

P2408 不同子串个数

对于每一个相同子串，我们都只在它出现的最大后缀中记录它的贡献。

对于每个后缀 $i$，出现在 $sa[rk_i + 1]$ 中的前缀不会被记录贡献，而没有出现的则会记录贡献，没被记录贡献的子串数为 $h[rk_i + 1]$。

因此，答案为 $\frac {n (n+1)} 2 - \sum\limits_{i=2}^n h_i$。不开 long long 见祖宗