深入理解后缀数组（C++后缀数组算法详解与实现）

为什么需要后缀数组？

后缀数组可以高效解决以下问题：

• 最长公共前缀（LCP）查询
• 子串搜索
• 重复子串检测
• 字符串匹配

相比后缀树，后缀数组更节省内存，且实现相对简单，是C++字符串处理中的常用技巧。

如何构建后缀数组？

最直观的方法是生成所有后缀，然后排序。但这种方法时间复杂度为 O(n² log n)，效率较低。我们可以使用更高效的 O(n log n) 算法——倍增法（Doubling Algorithm）。

倍增法核心思想

我们逐步对每个后缀的前 1、2、4、8... 个字符进行排序，每次利用上一轮的排序结果加速当前轮次。通过维护“排名”数组，我们可以快速比较两个后缀的大小。

C++ 实现代码

以下是完整的 C++后缀数组实现：

#include <iostream>#include <vector>#include <algorithm>#include <string>using namespace std;vector<int> buildSuffixArray(const string& s) {    int n = s.length();    vector<int> sa(n), rank(n), temp(n);    // 初始化：按单个字符排序    for (int i = 0; i < n; ++i) {        sa[i] = i;        rank[i] = s[i];    }    // 倍增    for (int k = 1; k < n; k *= 2) {        // 按 (rank[i], rank[i+k]) 排序        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);        // 重新计算 rank        temp[sa[0]] = 0;        for (int i = 1; i < n; ++i) {            temp[sa[i]] = temp[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) ? 1 : 0);        }        rank = temp;    }    return sa;}int main() {    string s = "banana";    auto sa = buildSuffixArray(s);    cout << "后缀数组: ";    for (int idx : sa) {        cout << idx << " ";    }    cout << endl;    return 0;}

运行上述代码，输出为：

后缀数组: 5 3 1 0 4 2

这正是我们前面手动计算的结果！

算法复杂度分析

• 时间复杂度：O(n log² n)（使用 std::sort）；若使用基数排序可优化至 O(n log n)
• 空间复杂度：O(n)

应用场景举例

假设你需要在一个大型DNA序列中查找某个基因片段，使用后缀数组实现可以快速定位所有出现位置。此外，在文本编辑器中实现“查找所有匹配项”功能时，后缀数组也是底层关键技术之一。

总结

通过本教程，你已经掌握了：

• 后缀数组的定义与作用
• 倍增法构建后缀数组的原理
• C++ 实现代码及运行示例

后缀数组是字符串算法中的基石之一。掌握它，将为你打开高效字符串处理的大门。建议你动手敲一遍代码，加深理解！

如果你觉得本文有帮助，欢迎分享给正在学习 C++字符串处理 的朋友！