后缀数组 (Suffix Array) 模板详解

靖2025-01-072025-01-07

后缀数组 (Suffix Array) 模板详解

1. 简介

后缀数组是一种重要的字符串数据结构，它将字符串的所有后缀按字典序排序后得到的数组。配合最长公共前缀（LCP）数组，可以解决许多字符串问题。

主要特点：

O(nlogn) 的构建时间
可以处理字符串的所有后缀
支持高效的字符串匹配
可以解决最长公共子串等问题

2. 实现原理

2.1 基本概念

后缀数组 (SA)：
- 存储后缀开始位置的有序数组
- 按后缀字典序排序
名次数组 (Rank)：
- 每个后缀的排名
- SA 数组的逆映射
LCP数组：
- 相邻后缀的最长公共前缀
- 用于优化字符串匹配

2.2 核心策略

倍增算法：
- 逐步增加排序长度
- 利用已有排序信息
基数排序：
- 保证稳定性
- 提高排序效率

3. 模板代码

struct SuffixArray {
    int n;
    std::vector<int> sa, rk, lc;
    SuffixArray(const std::string &s) {
        n = s.length();
        sa.resize(n);
        lc.resize(n - 1);
        rk.resize(n);
        std::iota(sa.begin(), sa.end(), 0);
        std::sort(sa.begin(), sa.end(), [&](int a, int b) {
            return s[a] < s[b];
        });
        rk[sa[0]] = 0;
        for (int i = 1; i < n; ++i) {
            rk[sa[i]] = rk[sa[i - 1]] + (s[sa[i]] != s[sa[i - 1]]);
        }
        int k = 1;
        std::vector<int> tmp, cnt(n);
        tmp.reserve(n);
        while (rk[sa[n - 1]] < n - 1) {
            tmp.clear();
            for (int i = 0; i < k; ++i) {
                tmp.push_back(n - k + i);
            }
            for (auto i : sa) {
                if (i >= k) {
                    tmp.push_back(i - k);
                }
            }
            std::fill(cnt.begin(), cnt.end(), 0);
            for (int i = 0; i < n; ++i) {
                ++cnt[rk[i]];
            }
            for (int i = 1; i < n; ++i) {
                cnt[i] += cnt[i - 1];
            }
            for (int i = n - 1; i >= 0; --i) {
                sa[--cnt[rk[tmp[i]]]] = tmp[i];
            }
            std::swap(rk, tmp);
            rk[sa[0]] = 0;
            for (int i = 1; i < n; ++i) {
                rk[sa[i]] = rk[sa[i - 1]] + (tmp[sa[i - 1]] < tmp[sa[i]] || 
                    sa[i - 1] + k == n || tmp[sa[i - 1] + k] < tmp[sa[i] + k]);
            }
            k *= 2;
        }
        for (int i = 0, j = 0; i < n; ++i) {
            if (rk[i] == 0) {
                j = 0;
            } else {
                j -= j > 0;
                while (i + j < n && sa[rk[i] - 1] + j < n && 
                       s[i + j] == s[sa[rk[i] - 1] + j]) {
                    j++;
                }
                lc[rk[i] - 1] = j;
            }
        }
    }
};

4. 函数说明

4.1 成员变量

int n;                  // 字符串长度
std::vector<int> sa;    // 后缀数组
std::vector<int> rk;    // 名次数组
std::vector<int> lc;    // LCP数组

4.2 构造函数

输入：字符串 s
构建后缀数组和 LCP 数组
使用倍增算法实现

5. 时间复杂度分析

构建后缀数组：O(nlogn)
构建 LCP 数组：O(n)
空间复杂度：O(n)

6. 应用场景

字符串匹配
最长公共子串
重复子串查找
循环移位最小表示

7. 使用示例

7.1 构建后缀数组

string s = "banana";
SuffixArray sa(s);
// sa = [5,3,1,0,4,2]
// lc = [1,3,0,0,2]

7.2 查找最长重复子串

int findLongestRepeatedSubstring(const string& s) {
    SuffixArray sa(s);
    int maxLen = 0;
    for (int i = 0; i < s.length() - 1; i++) {
        maxLen = max(maxLen, sa.lc[i]);
    }
    return maxLen;
}