后缀数组是将字符串所有后缀按字典序排序后记录起始位置的数组，用于高效解决模式匹配、LCP、重复子串等问题；例如"banana"的SA为[5,3,1,0,4,2]，可通过直接排序实现，或用倍增法优化至O(n log²n)，结合LCP数组可拓展多种应用。
后缀数组（Suffix Array，简称 SA）是处理字符串问题的强大工具，相比后缀树更简洁、节省空间。它通过将字符串的所有后缀按字典序排序，记录其起始位置的索引，从而支持高效地完成模式匹配、最长公共前缀（LCP）、重复子串查找等任务。
什么是后缀数组
给定一个字符串 s，它的所有后缀是指从每个位置到末尾的子串。例如，字符串 "banana" 的后缀有：
- banana
- anana
- nana
- ana
- na
- a
将这些后缀按字典序排序后，得到新的顺序，后缀数组 SA 就是保存这些排序后的原起始下标。比如排序后第一个后缀是 "a"，起始于下标 5，所以 SA[0] = 5。
如何用C++实现基础后缀数组
最直接的方法是生成所有后缀，排序并记录原始位置。虽然时间复杂度为 O(n² log n)，但对于中等长度字符串足够实用。
立即学习“C++免费学习笔记（深入）”；
#include#include #include #include std::vector buildSuffixArray(const std::string& s) { int n = s.size(); std::vector sa(n); // 初始化：sa[i] = i for (int i = 0; i < n; ++i) sa[i] = i; // 按后缀字符串排序 std::sort(sa.begin(), sa.end(), [&s](int i, int j) { return s.substr(i) < s.substr(j); }); return sa; } // 示例使用 int main() { std::string s = "banana"; auto sa = buildSuffixArray(s); std::cout << "Suffix Array of \"" << s << "\": "; for (int idx : sa) std::cout << idx << " "; std::cout << "\n"; return 0; }
输出结果为：
Suffix Array of "banana": 5 3 1 0 4 2
对应后缀排序为：
"a", "ana", "anana", "banana", "na", "nana"
优化思路：倍增法 + 哈希（O(n log²n)）
对于更长字符串，可以使用倍增法（Doubling Method），每次比较前 2^k 个字符，配合 rank 数组进行排序，将复杂度降到 O(n log²n) 或 O(n log n)。
核心思想：
- 维护每个位置开始的长度为 k 的子串的排名
- 每次将 k 翻倍，利用上一轮的 rank 快速比较两个子串
- 用 pair
进行排序
这样避免了 substr 的高开销，适合处理较长字符串。
常见应用举例
有了后缀数组，结合 LCP（最长公共前缀）数组，可以解决很多问题：
- 查找子串出现次数：二分查找在 SA 中定位范围
- 最长重复子串：遍历相邻后缀的 LCP 最大值
- 最长回文子串：构造反串拼接后找 LCP
- 多字符串公共子串：标记来源后找跨组的最长 LCP
SA 是竞赛和实际工程中处理字符串匹配、压缩、生物信息等领域的重要工具。
基本上就这些。从简单实现入手，理解原理后再过渡到高效算法，能更好地掌握这一数据结构的本质。
