最近 NFLS 周赛，F 题需要后缀数组，我不会，光荣掉到 20+ 名。
打完后就去补习了相关知识，觉得很巧妙，就来写了一篇专栏
1. 后缀数组的定义
后缀数组（SA）保存的是一个字符串所有后缀的排序结果，其中第 SA[i] 表示所有后缀中第 $ i $ 小的后缀的开头位置。
与之相对的是名次数组 Rank，Rank[i] 表示以 $ i $ 开头的后缀排第几位。
举个栗子：
str: a a a b a a b a
SA: 8 1 5 2 6 3 7 4
Rank:2 4 6 8 3 5 7 1
2. 求法
有两种方法倍增和 DC3，但我太菜了，只会倍增算法。
2.1. 倍增
倍增，就是通过 $ i $ 步的答案推出 $ 2i $ 步的答案，从而在 $ O(\log n) $ 的时间内推出答案。那它跟后缀数组有什么关系呢？
假设我们已经求出了每个 $ i \sim i + 1 $ 的子串的 Rank：
str: a a a b a a b a
Rnk2:2 2 3 4 2 3 4 1
考虑将两个字符和两个字符拼在一起成为四个字符。
实际上，我们只需要将 Rank 拼在一起即可。为什么呢？
考虑将这样的二元组进行比较：
aaab Rank: (2, 3)
aaba Rank: (2, 4)
因为 Rank 反映了字典序情况，所以比较 Rank 相当于比较字典序
First: 2 = 2 相当于比较前两个字符的字典序
Second:2 < 4 相当于比较后两个字符的字典序
回到我们刚才的例子：
Rnk2:2 2 3 4 2 3 4 1
1st: 2 2 3 4 2 3 4 1
2nd: 3 4 2 3 4 1 0 0 （没有时视为 0，是最小的序列）
Rnk4:2 3 5 7 3 4 6 1
于是我们就不断把子串拼接拼接再拼接，拼接足够多次直到长度 $ \ge n $ 即可。
使用基数排序，我们就可以 $ O(n \log n) $ 求出答案。
2.2. DC3
<++>（待更）
3. 实际应用
<++>（待更）
标签：字符,loves,Algorithm,后缀,OI,Rank,拼接,数组,字典 From： https://www.cnblogs.com/AProblemSolver/p/18294777