倍增法构建后缀数组的核心逻辑是：以长度 $2^k$ 逐步倍增比较，每轮将后缀前 $2^k$ 字符拆分为两个 $2^{k-1}$ 段，利用上一轮已计算的 rank 值构成双关键字 $(\text{rank}[i], \text{rank}[i+k])$ 进行稳定计数排序，更新 sa 和 rank 数组，最终在 $O(n \log n)$ 时间内完成构造。
倍增法构建后缀数组的核心逻辑是什么
倍增法不是靠排序所有后缀字符串（那样是 O(n² log n)），而是按长度 2ᵏ 逐步比较：先按首字符排，再按前 2 个字符，再前 4 个……每次利用上一轮结果避免重复比较。关键在于，每个后缀的 2ᵏ 长度信息可拆成两个 2ᵏ⁻¹ 段——刚好对应上一轮已算好的 rank 值。
所以你真正要维护的是 sa（后缀起始位置数组）和 rank（每个位置开头的后缀当前排名），两者互为逆：满足 rank[sa[i]] == i。倍增每轮用 rank 快速生成新关键字对，再用计数排序重排 sa。
标准倍增实现里最容易错的三处细节
常见错误不是算法想错，而是边界或索引偏移写反：
-
sa数组下标是排名（0-based 排名），值是原字符串下标（0-based 位置），但很多模板把sa[0]当作最小后缀位置——这没错，但后续用rank时若没初始化rank[sa[i]] = i就会全乱 - 当计算长度为
2*k的关键字对时，第二段起始位置是i + k，一旦i + k >= n，应设其rank为 -1（或 0，但必须统一小于所有合法 rank），否则计数排序会把越界位置排到前面 - 计数排序必须稳定，且要倒序遍历
sa（从大到小），否则相同关键字的后缀顺序会被颠倒——这是倍增法正确性的硬性要求，不是优化项
一个极简可运行的倍增 SA 构建片段（C++17）
void build_sa(const string& s, vector<int>& sa) {
int n = s.size();
sa.resize(n);
vector<int> rank(n), tmp(n);
// 初始化：长度为 1
for (int i = 0; i < n; ++i) {
sa[i] = i;
rank[i] = s[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
// 正确做法是先按第二关键字排序（用桶），再按第一关键字稳定计数排序
sort(sa.begin(), sa.end(), cmp);
tmp[sa[0]] = 0;
for (int i = 1; i < n; ++i) {
tmp[sa[i]] = tmp[sa[i-1]] + (cmp(sa[i-1], sa[i]) ? 1 : 0);
}
rank.swap(tmp);
}
}
⚠️ 这段用了 sort 仅用于理解结构；真实高性能版本必须手写双关键字计数排序（复杂度 O(n) 每轮），否则整体退化为 O(n log² n)。核心是：先按第二关键字（即 i+k 处 rank）分桶，再对每个桶内按第一关键字（rank[i]）做前缀和式计数排序。
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
立即学习“C++免费学习笔记（深入）”；
什么时候不该用倍增法——性能与替代方案
倍增法时间 O(n log n)，空间 O(n)，适合 n ≤ 1e6 的一般场景。但它有明显短板：
- 字符串含大量重复子串时，常数较大；
rank数组频繁更新导致缓存不友好 - 无法在线构造；也不支持动态插入字符
- 当 n 超过 5e6，DC3 或 SA-IS 更稳——前者理论 O(n)，后者实测更快，但代码量翻倍
- 如果只需求
height数组（LCP），可考虑先建 SA 再用 Kasai 算法，别试图在倍增过程中“顺手”算 height，容易错且不省事
真正卡常时，连 memset 初始化都得按需清零，rank 和 tmp 数组复用比反复 new 更关键——这些细节不体现在公式里，但决定你能不能过 OJ 的 1s 时限。
