c++kquote>后缀数组是字符串所有后缀按字典序排序后的起始下标数组；例如”ababa”的后缀数组为[4,0,2,1,3]；可通过暴力法（O(n²log n)）或倍增算法（O(n log²n)）构建，后者利用rank数组分轮按长度倍增排序。
什么是后缀数组？
后缀数组（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 #include #include #include #includestd::vector build_suffix_array(const std::string& s) {int n = s.size();std::vector sa(n), rank(n), tmp_rank(n);for (int i = 0; i < n; ++i) {sa[i] = i;rank[i] = s[i];}
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++免费学习笔记（深入）”；
int main() {std::string s = "ababa";auto sa = build_suffix_array(s);std::cout
小结与提醒
后缀数组本身只是排序结果，真正用起来常配合 height 数组（相邻后缀的 LCP）做字符串匹配、重复子串、最长回文子串等。这个版本没实现 height，但 SA 是基础。
实际项目中可考虑用现成库如 libdivsufsort，但手写倍增有助于吃透字符串算法逻辑。
基本上就这些 —— 不复杂但容易忽略边界和 rank 更新细节。
以上就是c++++如何实现一个简单的后缀数组(Suffix Array)_c++字符串处理高级算法【源码】的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1489635.html
微信扫一扫 
支付宝扫一扫 
