后缀数组是字符串所有后缀按字典序排序后的起始下标数组；直接用std::sort对后缀子串排序会导致每次比较最坏O(n)、总复杂度O(n²logn)，大规模数据不可行。
后缀数组是什么，为什么不能直接用 std::sort
后缀数组（Suffix Array）是字符串所有后缀按字典序排序后的起始下标数组。比如 "ababa" 的后缀有 "ababa"、"baba"、"aba"、"ba"、"a"，排序后下标顺序是 [4, 2, 0, 3, 1]。直接用 std::sort 对所有后缀子串排序看似简单，但每次比较最坏要 O(n) 时间，总复杂度退化到 O(n² log n)，对长度 >10⁵ 的字符串就卡死。
倍增法（Doubling）构造：兼顾可读与实用性
倍增法是教学和中等规模数据（n ≤ 5×10⁵）最实用的选择。它不依赖 SA-IS 等黑盒算法，逻辑清晰，且 C++ 标准库足够支撑实现。
核心思想：按长度为 2^k 的前缀排序，逐步合并两个长度为 2^{k-1} 的已排序段。每轮用 pairstd::sort 排这些 pair —— 这次比较是 O(1) 的。
- 初始化：每个后缀按首字符排序，
sa[i]存下标，rank[i]存该位置字符的字典序排名（相同字符同排名） - 循环
k = 1, 2, 4, ...直到k ≥ n：构造新 pair 数组{rank[i], rank[i+k]}，用std::sort对下标i排序；再重新分配rank（相同 pair 视为同排名） - 注意边界：当
i + k ≥ n时，后半段视为最小值（可用 -1 或 0，但必须统一且小于所有有效 rank）
示例关键片段：
立即学习“C++免费学习笔记（深入）”；
vector<int> sa(n), rank(n), tmp_rank(n);
iota(sa.begin(), sa.end(), 0);
sort(sa.begin(), sa.end(), [&](int i, int j) { return s[i] < s[j]; });
// 初始化 rank
for (int i = 0; i < n; i++) {
rank[sa[i]] = (i && s[sa[i]] == s[sa[i-1]]) ? rank[sa[i-1]] : i;
}
for (int k = 1; k < n; k *= 2) {
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;
};
sort(sa.begin(), sa.end(), cmp);
// 重算 rank
tmp_rank[sa[0]] = 0;
for (int i = 1; i < n; i++) {
int cur = (rank[sa[i]] == rank[sa[i-1]]) &&
((sa[i]+k<n ? rank[sa[i]+k] : -1) == (sa[i-1]+k<n ? rank[sa[i-1]+k] : -1));
tmp_rank[sa[i]] = tmp_rank[sa[i-1]] + (cur ? 0 : 1);
}
rank.swap(tmp_rank);
}
SA-IS 算法：只在必须时才上手
如果字符串长度超过 10⁶，或需在线构建（如多模式匹配预处理），倍增法常超时，这时得用线性时间的 SA-IS。但它不是“调个函数就行”的东西：需要理解 L-type/S-type 分类、诱导排序、bucket 划分，且极易因边界判断出错导致无限循环或越界访问。
- 不要自己从零手写 SA-IS —— 容易漏掉
s[n] = 0（哨兵）、bucket大小计算错误、诱导顺序颠倒等细节 - 生产环境建议直接用成熟实现，如
libsais（C 接口，C++ 可封装）或divsufsort；它们经过大量测试，支持uint8_t*输入、内存池控制、并行加速 - 若真要调试 SA-IS，务必先用小样例（如
"aabaa"）手推每轮type数组和 bucket 填充过程，否则看代码等于看天书
常见坑：字符串结尾、类型、稳定性
几乎所有新手实现都会栽在这三点上：
-
std::string默认无结尾'\0'，而多数 SA 构造逻辑（尤其 SA-IS）隐含要求字符串以最小字符结尾。解决方法：要么手动 push_back(0)，要么在比较逻辑里显式处理越界（如前面倍增法中的-1） - 用
int存下标和 rank 没问题，但若字符串长度接近INT_MAX（极罕见），或需跨平台兼容，应改用size_t或long long，否则i + k溢出未定义 -
std::sort不稳定，但倍增法中同一轮内相同 pair 的相对顺序无关紧要；不过若你在中间插入调试输出或自定义结构体，误加了非严格弱序比较（比如漏写==分支），会导致std::sort崩溃或返回乱序结果
真正难的从来不是写完，而是验证结果是否正确——建议随手加一个 verify_sa() 函数：对每个 i，检查 s.substr(sa[i]) <= s.substr(sa[i+1])（用 string::compare 避免构造子串），并确认 sa 是 0..n-1 的排列。
