后缀数组 (Suffix Array)¶

后缀数组（Suffix Array, SA）是字符串处理领域极其强大的数据结构，用于将字符串的所有后缀按照字典序进行排序。

核心定义¶

对于长度为 \(n\) 的字符串 \(s\)：

sa[i]：排名为 \(i\) 的后缀的起始下标（\(0 \le i < n\)）。
rk[i]：起始下标为 \(i\) 的后缀的字典序排名，满足 \(rk[sa[i]] = i\)。
lcp[i]（或 height[i]）：后缀 \(sa[i]\) 与前一个排名的后缀 \(sa[i-1]\) 的最长公共前缀（LCP）长度。

关键定理：任意两后缀 \(sa[i]\) 与 \(sa[j]\)（设 \(i < j\)）的 LCP 满足：

\[ \operatorname{LCP}(sa[i], sa[j]) = \min_{k = i + 1}^{j} lcp[k] \]

结合 ST 表，可在 \(\mathcal{O}(1)\) 时间内回答任意两个后缀的最长公共前缀。

模版实现 (倍增 + 基数排序 \(\mathcal{O}(n \log n)\) + Kasai 算法)¶

#include <vector>
#include <string>
#include <algorithm>
#include <cmath>

struct SuffixArray {
    int n;
    std::string s;
    std::vector<int> sa;   // sa[i]: 排名第 i 的后缀起始位置
    std::vector<int> rk;   // rk[i]: 后缀 i 的排名
    std::vector<int> lcp;  // lcp[i]: LCP(sa[i], sa[i-1])
    std::vector<std::vector<int>> st; // ST 表维护区间 LCP 最小值
    std::vector<int> lg;

    SuffixArray(const std::string &str) : n(str.size()), s(str), sa(n), rk(n), lcp(n) {
        build_sa();
        build_lcp();
        build_rmq();
    }

    void build_sa() {
        int m = 128; // 初始字符集大小
        std::vector<int> cnt(std::max(n, m) + 1, 0), x(n), y(n);

        for (int i = 0; i < n; ++i) cnt[x[i] = s[i]]++;
        for (int i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
        for (int i = n - 1; i >= 0; --i) sa[--cnt[x[i]]] = i;

        for (int k = 1; k < n; k <<= 1) {
            int p = 0;
            for (int i = n - k; i < n; ++i) y[p++] = i;
            for (int i = 0; i < n; ++i) if (sa[i] >= k) y[p++] = sa[i] - k;

            std::fill(cnt.begin(), cnt.begin() + m + 1, 0);
            for (int i = 0; i < n; ++i) cnt[x[y[i]]]++;
            for (int i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
            for (int i = n - 1; i >= 0; --i) sa[--cnt[x[y[i]]]] = y[i];

            std::swap(x, y);
            p = 1;
            x[sa[0]] = 0;
            for (int i = 1; i < n; ++i) {
                x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && 
                           (sa[i] + k < n ? y[sa[i] + k] : -1) == (sa[i - 1] + k < n ? y[sa[i - 1] + k] : -1)) 
                           ? p - 1 : p++;
            }
            if (p >= n) break;
            m = p;
        }

        for (int i = 0; i < n; ++i) rk[sa[i]] = i;
    }

    // Kasai 算法计算 height / lcp 数组，时间复杂度 O(n)
    void build_lcp() {
        int k = 0;
        for (int i = 0; i < n; ++i) {
            if (rk[i] == 0) {
                lcp[0] = 0;
                continue;
            }
            if (k > 0) k--;
            int j = sa[rk[i] - 1];
            while (i + k < n && j + k < n && s[i + k] == s[j + k]) {
                k++;
            }
            lcp[rk[i]] = k;
        }
    }

    // 构建 RMQ ST 表，支持 O(1) 查询任意两后缀的 LCP
    void build_rmq() {
        int K = std::__lg(n) + 1;
        st.assign(K, std::vector<int>(n));
        lg.assign(n + 1, 0);
        for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;

        st[0] = lcp;
        for (int j = 1; j < K; ++j) {
            for (int i = 0; i + (1 << j) <= n; ++i) {
                st[j][i] = std::min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
            }
        }
    }

    // 查询原串中以 i 和 j 开始的两后缀的 LCP 长度 (0-indexed)
    int get_lcp(int i, int j) const {
        if (i == j) return n - i;
        int l = rk[i], r = rk[j];
        if (l > r) std::swap(l, r);
        l++; // lcp[l+1...r] 的区间最小值
        int k = lg[r - l + 1];
        return std::min(st[k][l], st[k][r - (1 << k) + 1]);
    }
};

经典应用¶

1. 求不同子串的总数量¶

长度为 \(n\) 的字符串总共有 \(\frac{n(n + 1)}{2}\) 个子串。每个后缀 \(sa[i]\) 贡献其长度 \(n - sa[i]\) 个前缀子串，其中有 \(lcp[i]\) 个与前一后缀重复。

\[ \text{不同子串个数} = \frac{n(n + 1)}{2} - \sum_{i = 1}^{n - 1} lcp[i] \]

long long count_distinct_substrings(const SuffixArray &sa) {
    long long total = 1LL * sa.n * (sa.n + 1) / 2;
    for (int i = 1; i < sa.n; ++i) {
        total -= sa.lcp[i];
    }
    return total;
}

2. 子串匹配 / 统计出现次数¶

由于所有后缀在 sa 数组中是有序的，所有包含模式串 \(P\) 的后缀必定在 sa 中构成一个连续区间 \([L, R]\)。可以在 sa 数组上以 \(\mathcal{O}(|P| \log n)\) 两次二分查找定位该区间的左右端点。

LeetCode 经典真题精选与题解提示¶

LeetCode 1163 - 按字典序排在最后的子串 (Last Substring in Lexicographical Order) 困难
提示

字典序最大后缀定理。
- 原理：对任意非全后缀的子串 \(t\)，延长它得到的后缀 \(t + \dots\) 字典序严格大于 \(t\)。因此全串字典序最大的子串必然是某个完整的后缀！
- 利用后缀数组，字典序最大的后缀正是排在最后的 sa[n - 1] 对应的后缀，截取 \(s[sa[n - 1] \dots n - 1]\) 即可；本题亦可用双指针（类最小表示法）实现严格 \(\mathcal{O}(n)\) 扫描。
LeetCode 1044 - 最长重复子串 (Longest Duplicate Substring) 困难
提示

\(lcp\) 数组最大值快速求解。
- 最长重复子串等价于任意两不同后缀的最长公共前缀 (LCP)。
- 由后缀数组性质，任意两后缀的 LCP 长度等于其间连续 \(lcp\) 值的最小值，因此全局最大 LCP 必然在某对字典序相邻的后缀之间取得。
- 构建 SA 与 \(lcp\) 数组后，直接扫描找出 \(\max_{i=1}^{n - 1} lcp[i]\) 及其对应的后缀起始位置，无需二分哈希，总时间复杂度严格稳定为 \(\mathcal{O}(n \log n)\)。
LeetCode 1754 - 构造字典序最大的合并字符串 (Largest Merge Of Two Strings) 中等
提示

后缀字典序比较贪心。
- 两个字符串 \(w_1, w_2\) 每次取首字符，当 \(w_1[i] == w_2[j]\) 时，必须选择剩余后缀字典序更大的那一个字符，才能保证后续高位字符尽早出现。
- 可预先将两串用特殊字符隔开拼接计算后缀数组，利用 \(rk\) 数组在 \(\mathcal{O}(1)\) 时间内完成每次贪心比较。