C++后缀数组实现（从零开始掌握后缀数组构建与应用）

C++后缀数组实现方法

实现后缀数组有多种方法，最简单的是使用标准库的排序函数（时间复杂度 O(n² log n)），适合学习理解；更高效的方法如倍增算法（O(n log n)）或 SA-IS 算法（O(n)），但较为复杂。本文先介绍基础实现，便于初学者掌握核心思想。

方法一：暴力排序法（适合入门）

我们创建一个索引数组，然后根据对应后缀的字典序进行排序。

#include <iostream>#include <vector>#include <algorithm>#include <string>std::vector<int> buildSuffixArray(const std::string& s) {    int n = s.length();    std::vector<int> suffixArray(n);        // 初始化索引：0, 1, 2, ..., n-1    for (int i = 0; i < n; ++i) {        suffixArray[i] = i;    }        // 根据后缀的字典序对索引排序    std::sort(suffixArray.begin(), suffixArray.end(),        [&s](int a, int b) {            return s.substr(a) < s.substr(b);        }    );        return suffixArray;}int main() {    std::string text = "banana";    auto sa = buildSuffixArray(text);        std::cout << "后缀数组: ";    for (int idx : sa) {        std::cout << idx << " ";    }    std::cout << std::endl;        return 0;}

这段代码虽然简洁，但由于每次比较都调用 substr（时间复杂度 O(n)），整体效率较低。但它清晰展示了C++后缀数组实现的基本逻辑，非常适合初学者理解。

方法二：倍增算法（推荐进阶）

为了提升效率，我们可以使用倍增法（Doubling Algorithm），通过逐步比较长度为 1, 2, 4, 8... 的前缀来排序后缀，时间复杂度为 O(n log n)。

#include <iostream>#include <vector>#include <algorithm>#include <string>std::vector<int> buildSuffixArrayDoubling(const std::string& s) {    int n = s.size();    std::vector<int> sa(n), rank(n), new_rank(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]) 对 sa 排序        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;        };        std::sort(sa.begin(), sa.end(), cmp);                // 重新计算 rank        new_rank[sa[0]] = 0;        for (int i = 1; i < n; ++i) {            new_rank[sa[i]] = new_rank[sa[i-1]] + (cmp(sa[i-1], sa[i]) ? 1 : 0);        }        rank = new_rank;                if (rank[sa[n-1]] == n - 1) break; // 所有 rank 唯一，提前结束    }        return sa;}

这个版本避免了重复生成子串，显著提升了性能，是实际项目中常用的后缀数组算法详解实现方式。

应用场景与总结

后缀数组在C++字符串处理中用途广泛，例如：

• 快速查找子串（配合二分搜索）
• 求两个字符串的最长公共子串
• 文本压缩（如 BWT 变换）

通过本教程，你已经掌握了后缀数组入门教程的核心内容：从定义理解到 C++ 实现。建议先用暴力法理解原理，再尝试倍增法优化。多加练习，你就能灵活运用这一强大工具！

祝你在算法学习之路上越走越远！