把字符串的尾巴排个队 —— 后缀数组入门

想象一下，你有一串英文单词“banana”，它的所有“尾巴”就是：banana、anana、nana、ana、na、a。这些小尾巴就像班上同学的名字，如果按字母顺序给它们排个队，你会得到一个新顺序：a、ana、anana、banana、na、nana。排好队后，我们就能快速发现秘密：比如哪两个尾巴共享最长的开头（"ana"和"anana"共享"ana"），或者哪个小段子（子串）在整个单词里出现得最多（“ana”出现了两次）。这个排好队的列表，就叫做后缀数组（Suffix Array）。计算机科学家用它来解决很多字符串问题，比如找重复单词、压缩数据、甚至在DNA里找相同片段。

1. 什么是后缀？

后缀就是一个字符串从某个位置一直跑到末尾的子串。比如字符串 s = "chess"，它有这些后缀：

从位置0开始："chess"
从位置1开始："hess"
从位置2开始："ess"
从位置3开始："ss"
从位置4开始："s"

一共 5 个后缀（字符串长度是多少，就有多少个后缀）。把它们记下来，就像把每个人的名字从中间切一刀，留下后半截。

生活中的例子：你们班的学号是按入学顺序排的。现在要按姓名拼音重新排学号列表，这就像后缀数组——把每个同学（后缀）按拼音（字典序）排序，然后记录下它们原来的学号（起始位置）。

2. 后缀数组是什么？

后缀数组是一个整数数组，通常记作 SA（Suffix Array）。SA[i] 表示排在第 i 位的后缀在原字符串中的起始位置（下标从0开始）。比如字符串 "banana"，所有后缀排序后：

排名	后缀内容	起始位置
0	a	5
1	ana	3
2	anana	1
3	banana	0
4	na	4
5	nana	2

所以 SA = {5, 3, 1, 0, 4, 2}。注意：排名从0开始。有的教材从1开始，但只要保持一致就行。

有了这个数组，我们能快速回答：

两个后缀的最长公共前缀（LCP）是多少？例如 SA[1] 和 SA[2] 对应的 "ana" 和 "anana"，公共部分是 "ana"，长度为3。
出现次数最多的子串：在 "banana" 中，子串 "ana" 出现了两次（位置1和3），通过比较相邻后缀的公共前缀就能发现。

3. 用简单方法构造后缀数组（适合理解）

最直接的办法：生成所有后缀，然后用 sort 按字典序排序。虽然速度慢（O(n² log n)），但逻辑一目了然，适合初学者理解核心思想。

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s = "banana";                // 原字符串
    int n = s.size();                   // 字符串长度
    vector<pair<string, int>> suffixes; // 存每个后缀（字符串+起始位置）
    for (int i = 0; i < n; i++) {
        suffixes.push_back({s.substr(i), i}); // 生成从i开始的后缀
    }
    sort(suffixes.begin(), suffixes.end());   // 按字典序排序（先比字符串，字符串相同才比第二个？这里pair默认先比first，所以排序正确）
    cout << "后缀数组 (SA): ";
    for (auto &p : suffixes) {
        cout << p.second << " ";              // 输出起始位置
    }
    cout << endl;
    // 输出: 5 3 1 0 4 2
    return 0;
}

解释：substr(i) 会从 i 截取到末尾，生成一个临时字符串，放进 pair 里。sort 按字典序比较两个后缀字符串，排好序后，p.second 就是原来的位置。

注意：pair 的排序规则是：先比较 first（后缀字符串），如果相等再比较 second（位置）。因为不同后缀的字符串一定不相等（长度不同或内容不同），所以位置不会影响排序。

4. 常见错误和注意事项

新手很容易遇到下面几个小坑：

4.1 把下标搞乱

后缀数组的起始位置通常从0开始，和C++字符串下标一致。有的OI题目里习惯用1-based（位置从1开始），写代码前一定要看清楚题目要求，或者统一在输出时+1。

4.2 误以为 `substr` 很快

用 substr 生成每个后缀会复制整个后缀字符串，总复杂度 O(n²)，对于长度超过1000的字符串就非常慢。真正的比赛代码会用倍增法或基数排序，但思想一样：每次根据前两个字符的排名，快速排序。

4.3 对字典序理解不深

字典序比较：先比第一个字符，小的排在前面；如果相同，比下一个，直到比出大小。如果其中一个字符串是另一个的前缀，那么短的那个排在前面。比如 "a" 排在 "ab" 前面，因为 "a" 比完后没有字符了，认为 "a" 更小。C++的 string 比较就是按这个规则。

5. 完整示例：输出后缀数组+展示每个后缀

下面是一个完整的程序，你输入一个单词，它就会输出后缀数组和每个后缀的内容，方便你对照检查。

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;                           // 原字符串
    cout << "请输入一个单词: ";
    cin >> s;
    int n = s.size();                   // 长度
    vector<pair<string, int>> suffixes; // 存放（后缀字符串，起始位置）
    for (int i = 0; i < n; i++) {
        suffixes.push_back({s.substr(i), i}); // 生成所有后缀
    }
    sort(suffixes.begin(), suffixes.end());   // 字典序排序

    cout << "后缀数组 (起始位置): ";
    for (auto &p : suffixes) {
        cout << p.second << " ";
    }
    cout << endl;

    cout << "按排序顺序的后缀:" << endl;
    for (auto &p : suffixes) {
        cout << "位置 " << p.second << " : " << p.first << endl;
    }
    return 0;
}

运行示例（输入 "suffix"）：

请输入一个单词: suffix
后缀数组 (起始位置): 2 4 1 5 3 0 
按排序顺序的后缀:
位置 2 : ffix
位置 4 : ix
位置 1 : uffix
位置 5 : x
位置 3 : fix
位置 0 : suffix

对照一下：原串 "suffix" 下标从0开始，后缀有：

0: suffix
1: uffix
2: ffix
3: fix
4: ix
5: x

排序后，"ffix" 最小，然后是 "ix"，"uffix"，"x"，"fix"，最后 "suffix"。输出的位置顺序是 2 4 1 5 3 0，和上图一致。

6. 后缀数组有什么用？

找最长重复子串：比如在 "ababa" 中，重复两次的最长子串是 "aba"。如何用后缀数组找？只需扫描相邻的两个后缀，计算它们的最长公共前缀（LCP），取最大值。比如 "ababa" 的后缀排序后，相邻是 "a" 和 "aba"（公共1）、"aba" 和 "ababa"（公共3）、"ababa" 和 "ba"（公共0）……最大为3 → 子串"aba"。
统计不同子串的个数：每个后缀贡献 len - 排名前一个LCP。比如 "banana"，不同子串总数 = 所有后缀长度之和 - 相邻LCP和 = (6+5+4+3+2+1) - (1+3+0+2+0) = 21 - 6 = 15个。
字符串匹配：给定一个模式串，比如 "na"，可以在后缀数组上二分查找所有以 "na" 开头的后缀，快速统计出现次数。

7. 相关指引

学会了后缀数组的基本概念后，如果你还想深入了解，可以继续学习：

倍增法（O(n log n)构造）—— 真正的比赛写法，用倍增和基数排序取代 substr 和 sort。
高度数组 (Height Array) —— 记录排名相邻的两个后缀的最长公共前缀，是解决大部分问题的关键。
后缀自动机（SAM） —— 另一种强大的字符串数据结构，可以做更多花样。
字符串哈希 —— 用哈希值判断子串是否相等，配合后缀数组能快速解决很多问题。

试试用今天学到的知识，自己写一个程序，找出某个单词中出现次数最多的长度为2的子串吧！比如 "banana" 中 "na" 出现了两次，而 "an" 只出现了一次。相信你一定能搞定。

Happy coding! ?

后缀数组——把所有尾巴排个队