C++怎么实现一个后缀数组_C++处理字符串问题的强大数据结构SA

冰火之心 2025-12-13 00:00:00 次阅读

后缀数组是将字符串所有后缀按字典序排序后记录起始位置的数组，用于高效解决模式匹配、LCP、重复子串等问题；例如"banana"的SA为[5,3,1,0,4,2]，可通过直接排序实现，或用倍增法优化至O(n log²n)，结合LCP数组可拓展多种应用。

后缀数组（Suffix Array，简称 SA）是处理字符串问题的强大工具，相比后缀树更简洁、节省空间。它通过将字符串的所有后缀按字典序排序，记录其起始位置的索引，从而支持高效地完成模式匹配、最长公共前缀（LCP）、重复子串查找等任务。

什么是后缀数组

给定一个字符串 s，它的所有后缀是指从每个位置到末尾的子串。例如，字符串 "banana" 的后缀有：

banana
anana
nana
ana
na
a

将这些后缀按字典序排序后，得到新的顺序，后缀数组 SA 就是保存这些排序后的原起始下标。比如排序后第一个后缀是 "a"，起始于下标 5，所以 SA[0] = 5。

如何用C++实现基础后缀数组

最直接的方法是生成所有后缀，排序并记录原始位置。虽然时间复杂度为 O(n² log n)，但对于中等长度字符串足够实用。

#include 
#include 
#include 
#include 

std::vector buildSuffixArray(const std::string& s) {
    int n = s.size();
    std::vector sa(n);
    
    // 初始化：sa[i] = i
    for (int i = 0; i < n; ++i)
        sa[i] = i;

    // 按后缀字符串排序
    std::sort(sa.begin(), sa.end(), [&s](int i, int j) {
        return s.substr(i) < s.substr(j);
    });

    return sa;
}

// 示例使用
int main() {
    std::string s = "banana";
    auto sa = buildSuffixArray(s);

    std::cout << "Suffix Array of \"" << s << "\": ";
    for (int idx : sa)
        std::cout << idx << " ";
    std::cout << "\n";

    return 0;
}

输出结果为：
Suffix Array of "banana": 5 3 1 0 4 2

对应后缀排序为：
"a", "ana", "anana", "banana", "na", "nana"