后缀数组是字符串所有后缀按字典序排序后的起始下标数组；直接用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）
示例关键片段：
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]
<h3>SA-IS 算法：只在必须时才上手</h3>
<p>如果字符串长度超过 <code>10⁶</code>，或需在线构建（如多模式匹配预处理），倍增法常超时，这时得用线性时间的 <code>SA-IS</code>。但它不是“调个函数就行”的东西：需要理解 <code>L-type</code>/<code>S-type</code> 分类、诱导排序、bucket 划分，且极易因边界判断出错导致无限循环或越界访问。</p>
<ul>
<li>不要自己从零手写 SA-IS —— 容易漏掉 <code>s[n] = 0</code>（哨兵）、<code>bucket</code> 大小计算错误、诱导顺序颠倒等细节</li>
<li>生产环境建议直接用成熟实现，如 <code>libsais</code>（C 接口，C++ 可封装）或 <code>divsufsort</code>；它们经过大量测试，支持 <code>uint8_t*</code> 输入、内存池控制、并行加速</li>
<li>若真要调试 SA-IS，务必先用小样例（如 <code>"aabaa"</code>）手推每轮 <code>type</code> 数组和 bucket 填充过程，否则看代码等于看天书</li>
</ul>
<h3>常见坑：字符串结尾、类型、稳定性</h3>
<p>几乎所有新手实现都会栽在这三点上：</p>
<ul>
<li>
<code>std::string</code> 默认无结尾 <code>'\0'</code>，而多数 SA 构造逻辑（尤其 SA-IS）隐含要求字符串以最小字符结尾。解决方法：要么手动 push_back(0)，要么在比较逻辑里显式处理越界（如前面倍增法中的 <code>-1</code>）</li>
<li>用 <code>int</code> 存下标和 rank 没问题，但若字符串长度接近 <code>INT_MAX</code>（极罕见），或需跨平台兼容，应改用 <code>size_t</code> 或 <code>long long</code>，否则 <code>i + k</code> 溢出未定义</li>
<li>
<code>std::sort</code> 不稳定，但倍增法中同一轮内相同 pair 的相对顺序无关紧要；不过若你在中间插入调试输出或自定义结构体，误加了非严格弱序比较（比如漏写 <code>==</code> 分支），会导致 <code>std::sort</code> 崩溃或返回乱序结果</li>
</ul>
<p>真正难的从来不是写完，而是验证结果是否正确——建议随手加一个 <code>verify_sa()</code> 函数：对每个 <code>i</code>，检查 <code>s.substr(sa[i]) （用 string::compare 避免构造子串），并确认 <code>sa</code> 是 <code>0..n-1</code> 的排列。</code></p></int>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
