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

后缀数组是将字符串所有后缀按字典序排序后记录起始位置的数组，用于高效解决模式匹配、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)，但对于中等长度字符串足够实用。

立即学习“C++免费学习笔记（深入）”；

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

std::vector<int> buildSuffixArray(const std::string& s) {
    int n = s.size();
    std::vector<int> 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"

优化思路：倍增法 + 哈希（O(n log²n)）

对于更长字符串，可以使用倍增法（Doubling Method），每次比较前 2^k 个字符，配合 rank 数组进行排序，将复杂度降到 O(n log²n) 或 O(n log n)。

标签： c++ 后缀数组 go 大数据 工具 ai ios stream