倍增法构建后缀数组的核心逻辑是：以长度 $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。
标准倍增实现里最容易错的三处细节
常见错误不是算法想错，而是边界或索引偏移写反：
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
-
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
<p>⚠️ 这段用了 <code>sort</code> 仅用于理解结构；真实高性能版本必须手写双关键字计数排序（复杂度 O(n) 每轮），否则整体退化为 O(n log² n)。核心是：先按第二关键字（即 <code>i+k</code> 处 rank）分桶，再对每个桶内按第一关键字（<code>rank[i]</code>）做前缀和式计数排序。</p>
<h3>什么时候不该用倍增法——性能与替代方案</h3>
<p>倍增法时间 O(n log n)，空间 O(n)，适合 n ≤ 1e6 的一般场景。但它有明显短板：</p>
<ul>
<li>字符串含大量重复子串时，常数较大；<code>rank</code> 数组频繁更新导致缓存不友好</li>
<li>无法在线构造；也不支持动态插入字符</li>
<li>当 n 超过 5e6，DC3 或 SA-IS 更稳——前者理论 O(n)，后者实测更快，但代码量翻倍</li>
<li>如果只需求 <code>height</code> 数组（LCP），可考虑先建 SA 再用 Kasai 算法，别试图在倍增过程中“顺手”算 height，容易错且不省事</li>
</ul>
<p>真正卡常时，连 memset 初始化都得按需清零，<code>rank</code> 和 <code>tmp</code> 数组复用比反复 new 更关键——这些细节不体现在公式里，但决定你能不能过 OJ 的 1s 时限。</p></int></int>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
