后缀数组是字符串所有后缀按字典序排序后的起始下标数组；例如"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
- 重新编号得到新 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++免费学习笔记（深入）”；
int main() { std::string s = "ababa"; auto sa = build_suffix_array(s); std::cout
小结与提醒
后缀数组本身只是排序结果，真正用起来常配合 height 数组（相邻后缀的 LCP）做字符串匹配、重复子串、最长回文子串等。这个版本没实现 height，但 SA 是基础。
实际项目中可考虑用现成库如 libdivsufsort，但手写倍增有助于吃透字符串算法逻辑。
基本上就这些 —— 不复杂但容易忽略边界和 rank 更新细节。
