零、前言

字符串滚出 OI！这破字符串一题都做不下去了。

一、后缀数组

定义

考虑这样一个问题如何求解：

定义 $Suf_i$ 表示 $S_{[i,n]}$，即 $i$ 开始的一段后缀，其编号为 $i$。
对字符串 $S$ 的每个下标 $i$，求出 $Suf_i$ 在所有后缀中按字典序排序的排名。

• 记 $sa_i$ 为所有后缀排序之后，第 $i$ 小的后缀编号。
• 记 $rk_i$ 表示编号为 $i$ 的后缀排名是多少。

根据定义显然有 $sa_{rk_i} = rk_{sa_i} = i$，那么只要知道 $sa,rk$ 其一就可以线性地算出另一个。

求解

算法 1：暴力排序 $O(n^2 \log n)$

字符串比较复杂度 $O(n)$，排序复杂度 $O(n \log n)$，总复杂度 $O(n^2 \log n)$。
这不多说了。

算法 2：倍增 $O(n \log^2 n)$

考虑从小到大枚举 $2^k$，计算从 $i$ 开始往后长度为 $2^k$ 的字符串的 $rk^k$。
事实上，第 $k$ 轮的 $rk^k$ 可以由 $k-1$ 轮的 $rk^{k-1}$ 算出。
这个倍增的过程相当于把 $[i,i+2^{k-1}-1]$ 和 $[i+2^{k-1},i+2^k-1]$ 两个子串合并，也就相当于把 $rk^{k-1}_i$ 和 $rk^{k-1}_{i+2^{k-1}-1}$ 合并。
子串合并是首尾相接，那排名合并相当于合并为一个二元组，进行双关键字排序。
这样每次合并之后暴力 sort 复杂度为 $O(n \log n)$，外面套一层倍增，因此总复杂度 $O(n \log^2 n)$。

算法 3：倍增 + 计数排序 + 基数排序 $O(n \log n)$

倍增不能再优化了，现在瓶颈在于内部的 sort 排序。
能否将其优化为 $O(n)$？可以！
发现参与排序的元素都是上一轮的排名，因此值域是 $O(n)$，启发我们使用计数排序。
但是这是双关键字啊？也很简单，先对第二关键字排，再对第一关键字排，这里使用了基数排序的技巧。

算法 3 优化

优化 1

事实上不需要对第二关键字排序。
因为两个关键字都是上一轮排序的排名，即 $rk^{k-1}$，是单调的。
对于 $i+2^k \leq n$，它的第二关键字是有序的；对于 $i+2^k \gt n$，钦定它的第二关键字是 $-\infty$。
因此这个“排序”相当于把所有 $i+2^k \gt n$ 的下标移到最前面，其余的顺次往后移。

优化 2

实时计算计数排序的值域。

优化 3

如果值域已经是 $[1,n]$，那么说明每个后缀的排名都不同，因此再往后比较已经无意义。

算法 4：SA-IS $O(n)$；算法 5：DC3 $O(n)$

事实上 $O(n \log n)$ 的算法已经适用于绝大多数场景，因此 $O(n)$ 算法不再赘述。

代码 $O(n \log n)$

int sa[N], rk[N], pre[N], cnt[N];
int x[N], y[N]; //令 x 表示第一关键字排序的结果，y 表示第二关键字排序的结果
void init_SA() {
    int v = 128;
    for (int i = 0; i <= v; i++) cnt[i] = 0;
    for (int i = 1; i <= n; i++) ++cnt[ x[i] = (int)s[i] ];     //初始以 ASCII 作为排序依据
    for (int i = 1; i <= v; i++) cnt[i] += cnt[i - 1];          //计数排序，前缀和桶
    for (int i = n; i >= 1; i--) sa[ cnt[x[i]]-- ] = i;         //计数排序计算初始 sa 数组
    for (int len = 1; ; len <<= 1) {
        int tot = 0;
        for (int i = n - len + 1; i <= n; i++) y[++tot] = i;    //这些第二关键字默认为 -INF，直接平移到最前面
        for (int i = 1; i <= n; i++)    //注意 sa[i] 的含义是第 i 小的后缀编号，因此从小到大遍历是有序的，将它们按照第二关键字顺序插入即可
            if (sa[i] > len) y[++tot] = sa[i] - len;
        // y[i] 表示以第二关键字排序，第 i 小的后缀下标，则 x[y[i]] 表示再按照第一关键字排序的排名
        // 因此这里计数排序和开头有区别
        for (int i = 0; i <= v; i++) cnt[i] = 0;
        for (int i = 1; i <= n; i++) ++cnt[ x[i] ];
        for (int i = 1; i <= v; i++) cnt[i] += cnt[i - 1];
        for (int i = n; i >= 1; i--) sa[ cnt[x[y[i]]]-- ] = y[i], y[i] = 0;
        // 接下来需要更新新的 x 数组，且需要使用之前的 x 数组。
        // 因此可以直接把 x 和 y 交换，接下来 y 代表 old_x
        swap(x, y), tot = 0;
        for (int i = 1; i <= n; i++) {
            if (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + len] == y[sa[i - 1] + len]) x[sa[i]] = tot;
            else x[sa[i]] = ++tot;
        }
        v = tot;
        if (v == n) break;  //排好序了
    }
}

二、$\text{Height}$ 数组

定义

首先定义 $\text{LCP}(S,T)$ 表示 $S,T$ 两个字符串的最长公共前缀。
然后定义 $\text{Height}$ 数组：$height_i = \text{LCP}(suf_{sa_i}, suf_{sa_{i-1}})$。
特殊地，$height_1 = 0$。

性质

$$height_{rk_i} \geq height_{rk_{i-1}}-1$$
证明略。

应用 1：求两子串的 $\text{LCP}$

$$\text{LCP}(suf_{sa_i}, suf_{sa_j}) = \min\limits_{k=i+1}^{j} height_k$$

将两个子串的 LCP 转化为 RMQ 问题。

应用 2：比较两子串大小

假设两个子串分别为 $S[a,b]$ 和 $S[c,d]$，需要比较大小。
若 $\text{LCP}(suf_a,suf_c) \geq \min(b-a+1,d-c+1)$，则 $S[a,b] \lt S[c,d]$ 等价于 $b-a+1 \lt d-c+1$，因为一定满足一个是另一个的子串。
否则 $S[a,b] \lt S[c,d]$ 等价于 $rk_a \lt rk_c$。

应用 3：求所有子串去重后的数量

子串等价于后缀的前缀，考虑容斥，用总数减去重复数量。
则答案为 $\frac{n(n+1)}{2} - \sum\limits_{i=2}^{n} height_i$，因为 $height$ 的定义是 $\text{LCP}$ 长度。

应用 4：求出现了至少 $k$ 次的子串最大长度是多少

和上一个应用思路类似。由于子串等价于后缀的前缀，相当于在后缀排序之后一段连续后缀的公共前缀。
由公共前缀联想到 $\text{LCP}$，又因为至少出现 $k$ 次，因此只要在排序之后求所有长度为 $k-1$ 的区间的 $height$ 最大值即可。

求解

有了上面这条性质，就可以暴力求解了，复杂度是 $O(n)$。

代码

int ht[N];
void init_height() {
    for (int i = 1; i <= n; i++) rk[sa[i]] = i;
    for (int i = 1, j = 0, now = 0; i <= n; i++) {
        if (rk[i] == 1) { ht[rk[i]] = 0; continue; }    // 默认 h[1] = 0;
        j = sa[rk[i] - 1]; now = max(now - 1, 0);
        while (i + now <= n && j + now <= n && s[i + now] == s[j + now]) now++; //暴力扩展
        ht[rk[i]] = now;
    }
}

三、例题

1. AcWing 2715. 后缀数组

模板，求 sa 数组和 height 数组。

2. 洛谷 P2852 USACO06DEC Milk Patterns G

说实话这么小的数据范围一眼二分再开个 map 搞一下 hash 就能过去了。
但这毕竟是后缀数组练习题。
对应 height 数组应用 4，$\color{red}{\texttt{Sol}}$。

3. AcWing 2903. 差异

只要学会了 SA 就是简单题。$\color{red}{\texttt{Sol}}$。

4. AcWing 2720. 找相同字符

简单容斥转化为单字符串问题，然后和上一题一样的做法。$\color{red}{Sol}$。

5. AcWing 4758. 不同子串

height 数组应用 3。$\color{red}{\texttt{Sol}}$。

6. AcWing 2572. 生成魔咒

height 数组结合 ST 表。$\color{red}{\texttt{Sol}}$。

7. AcWing 3011. 甲苯先生和大中锋的字符串

height 数组结合单调队列、差分。$\color{red}{\texttt{Sol}}$。

8. AcWing 1004. 品酒大会

height 数组模型转化后结合并查集。$\color{red}{\texttt{Sol}}$。

9. AcWing 2991. 弦论

height 数组结合神秘二分。 $\color{red}{\texttt{Sol}}$。
貌似可以逐位确定？

10. AcWing 2933. 字符串

要是场上遇到这种题就算会做心态也先崩了，但其实码力要求并不高。
height 数组结合 ST 表、可持久化线段树、二分。$\color{red}{\texttt{Sol}}$。

11. AcWing 1006. 优秀的拆分

需要找到合适的 $O(n^2)$ 算法优化。部分 $O(n^2)$ 算法还优化不了 T_T。
可以 hash 干过去，但是 $O(n \log^2 n)$。$\color{red}{\texttt{Sol}}$。

学习链接

• OI-Wiki
• 大佬博客