后缀数组（SA）提高组

💡 核心思想

后缀数组是将字符串的所有后缀按字典序排序后得到的数组。SA[i] 表示排名第 i 的后缀的起始位置。LCP（最长公共前缀）数组记录相邻后缀的最长公共前缀长度。通过后缀数组 + LCP，可以在 O(log n) 时间内完成任意子串的比较，在 O(n) 时间内完成多种字符串统计问题。

🎯 直觉理解

想象你把一本书的所有可能的开头段落都列出来，然后按字典序排序。"后缀数组"就是这个排序后的列表。比如 "banana" 的后缀有：banana, anana, nana, ana, na, a。排序后：a, ana, anana, banana, na, nana。LCP 数组记录相邻两个后缀有多长的公共开头。

📝 算法流程

1. 倍增法构造 SA：
2. 第一轮按单个字符排序
3. 第 k 轮按长度为 2^k 的子串排序（用上一轮排名作为关键字）
4. 用计数排序或基数排序，复杂度 O(n log n)
5. 构造 LCP 数组（Height）：
6. 按排名顺序，利用 h[i] >= h[i-1] - 1 的性质 O(n) 构造

$$SA[i] = \text{排名第 }i\text{ 的后缀的起始位置}$$

$$LCP(i,j) = \min_{k=rank[i]+1}^{rank[j]} Height[k]$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;

// 后缀数组（倍增法）
struct SuffixArray {
    string s;
    vector sa, rank, height;
    int n;
    
    SuffixArray(const string& str) : s(str + '$'), n(s.size()) {
        sa.resize(n); rank.resize(n); height.resize(n);
        build();
    }
    
    void build() {
        // 初始按单个字符排序
        vector cnt(256, 0);
        for (char c : s) cnt[(unsigned char)c]++;
        for (int i = 1; i < 256; i++) cnt[i] += cnt[i-1];
        for (int i = n - 1; i >= 0; i--) sa[--cnt[(unsigned char)s[i]]] = i;
        
        rank[sa[0]] = 0;
        for (int i = 1; i < n; i++)
            rank[sa[i]] = rank[sa[i-1]] + (s[sa[i]] != s[sa[i-1]]);
        
        // 倍增
        for (int k = 1; rank[sa[n-1]] < n - 1; k <<= 1) {
            auto cmp = [&](int i, int j) {
                if (rank[i] != rank[j]) return rank[i] < rank[j];
                int ri = (i + k < n) ? rank[i + k] : -1;
                int rj = (j + k < n) ? rank[j + k] : -1;
                return ri < rj;
            };
            sort(sa.begin(), sa.end(), cmp);
            vector newRank(n);
            newRank[sa[0]] = 0;
            for (int i = 1; i < n; i++)
                newRank[sa[i]] = newRank[sa[i-1]] + cmp(sa[i-1], sa[i]);
            rank = newRank;
        }
        
        // 构造 Height (LCP)
        int h = 0;
        for (int i = 0; i < n - 1; i++) {
            int j = sa[rank[i] - 1];
            while (i + h < n && j + h < n && s[i + h] == s[j + h]) h++;
            height[rank[i]] = h;
            if (h > 0) h--;
        }
    }
};

int main() {
    SuffixArray sa("banana");
    for (int i = 0; i < sa.n; i++)
        cout << sa.sa[i] << " " << sa.s.substr(sa.sa[i]) << endl;
    return 0;
}

⚠️ 常见坑点

📚 相关题目