什么是后缀数组？
后缀数组（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
- 重新编号得到新 rank，gap *= 2
注意：
- 边界处理：i+gap 超出范围时，第二关键字设为 -1（最小）
- rank 数组可复用，用 vector
完整可运行代码（倍增 + sort 优化版）
// 编译：g++ -std=c++17 sa.cpp
#include#include #include #include #include std::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;}
int main() { std::string s = "ababa"; auto sa = build_suffix_array(s); std::cout
小结与提醒
后缀数组本身只是排序结果，真正用起来常配合 height 数组（相邻后缀的 LCP）做字符串匹配、重复子串、最长回文子串等。这个版本没实现 height，但 SA 是基础。
实际项目中可考虑用现成库如 libdivsufsort，但手写倍增有助于吃透字符串算法逻辑。
基本上就这些 —— 不复杂但容易忽略边界和 rank 更新细节。
;
}
