c++如何实现一个简单的后缀数组(Suffix Array)_c++字符串处理高级算法【源码】

什么是后缀数组？

后缀数组（Suffix Array）是一个整数数组，存储字符串所有后缀按字典序排序后的起始下标。比如字符串 “ababa”，它的5个后缀是：
“ababa”（0）、”baba”（1）、”aba”（2）、”ba”（3）、”a”（4）
按字典序排序后为：
“a”(4)、”ababa”(0)、”aba”(2)、”baba”(1)、”ba”(3)
所以后缀数组 SA = [4, 0, 2, 1, 3]

暴力法：适合理解原理

对长度为 n 的字符串，生成全部 n 个后缀，用 std::sort 配合自定义比较函数排序即可。时间复杂度 O(n² log n)，适用于 n ≤ 5000 的教学或小规模场景。

关键点：
– 后缀用 std::String_view 或 substr 避免拷贝
– 比较函数直接比后缀内容（不是下标）

• 用 std::vector 存下标索引
• 用 std::iota 初始化 [0,1,…,n-1]
• 排序时捕获原字符串引用，避免重复构造

倍增算法：O(n log²n) 实用实现

核心思想是分轮排序：先按长度为 1 的前缀排，再按长度为 2 的前缀排，然后是 4、8……直到 ≥n。每轮用上一轮的排名作为“第一关键字”，右半段排名作为“第二关键字”，用基数排序或 std::sort 稳定排序。

简化版步骤（不写完整基数排序）：
– 维护 rank[i] 表示以 i 开头的后缀在当前长度下的排名
– 每轮构造 pair，对所有合法 i 排序
– 重新编号得到新 rank，gap *= 2

注意：
– 边界处理：i+gap 超出范围时，第二关键字设为 -1（最小）
– rank 数组可复用，用 vector> 临时存键值对

完整可运行代码（倍增 + sort 优化版）

// 编译：g++ -std=c++17 sa.cpp

#include <iostream> #include <vector> #include <string> #include <algorithm> #include <utility> <p>std::vector<int> build_suffix_array(const std::string& s) { int n = s.size(); std::vector<int> sa(n), rank(n), tmp_rank(n); for (int i = 0; i < n; ++i) { sa[i] = i; rank[i] = s[i]; }</p><pre class="brush:php;toolbar:false;">for (int gap = 1; gap < n; gap *= 2) {     auto cmp = [&](int i, int j) {         if (rank[i] != rank[j]) return rank[i] < rank[j];         int ri = (i + gap < n) ? rank[i + gap] : -1;         int rj = (j + gap < n) ? rank[j + gap] : -1;         return ri < rj;     };     std::sort(sa.begin(), sa.end(), cmp);      tmp_rank[sa[0]] = 0;     for (int i = 1; i < n; ++i) {         tmp_rank[sa[i]] = tmp_rank[sa[i-1]] + (cmp(sa[i-1], sa[i]) ? 1 : 0);     }     rank.swap(tmp_rank); } return sa;

}

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

SkyReels

SkyReels是全球首个融合3D引擎与生成式ai的AI视频创作平台

1252

查看详情

int main() { std::string s = “ababa”; auto sa = build_suffix_array(s); std::cout

小结与提醒

后缀数组本身只是排序结果，真正用起来常配合 height 数组（相邻后缀的 LCP）做字符串匹配、重复子串、最长回文子串等。这个版本没实现 height，但 SA 是基础。

实际项目中可考虑用现成库如 libdivsufsort，但手写倍增有助于吃透字符串算法逻辑。

基本上就这些 —— 不复杂但容易忽略边界和 rank 更新细节。