后缀数组是什么
后缀数组就是主要处理字符串后缀问题的，它的实现算法主要有两种：倍增法和 DC3，复杂度分别是 \(O(n\log n)\) 和 \(O(n)\)。这里由于 DC3 代码答辩且难以理解，我就只写了倍增法的实现。
例题引入
P3809 【模板】后缀排序
题目大意
读入一个长度为 \(n\) 的由大小写英文字母或数字组成的字符串，把这个字符串的所有非空后缀按字典序从小到大排序，然后按顺序输出后缀的第一个字符在原串中的位置。位置编号为 \(1\) 到 \(n\)。
前置芝士
算法
后缀数组记录的就是字符串第 \(i\) 个后缀的排名。
比如一个字符串 \(S=abaababa\) 的后缀就是：
如果我们暴力去提取出 \(S\) 的所有后缀在给它排序显然是不行的，因为它的时间复杂度是 \(O(n^2\log n)\) 的。
倍增法
既然单纯的暴力不行，我们就需要考虑用倍增来处理。
倍增法的主要思想是：
每次将所有后缀按照前 \(2^k\) 个字符排序，最后得出所有后缀的排序。
这样问题就转化为了:现在已知所有后缀关于前 \(2^{k−1}\) 个字符的排序，要对所有后缀排序按前 \(2^k\) 个字符排序。
那么我们就可以将前 \(2^k\) 个字符分为两部分，每一部分的长度都是 \(2^{k−1}\)，并且这两部分按照字典序排序后的名次是已知的。
这里我们定义前一部分的排名为第一关键字 \(key1\)，后一部分的排名为第二关键字 \(key2\)。然后每次按照关键字进行排序，更新 \(rank\) 数组，得到新的排名。
这就是倍增法对后缀数组的处理，比如当处理 \(S=aabaaaab\) 时过程如图：
注意，这里处理第一第二关键字排序时，需要先按第一关键字的大小排序，再用第二关键字来排，其思想与基数排序很像。
由于字符串的每个后缀都是不同的(至少长度不同)，所以最后得到的 \(rank\) 数组里的数必定是互不相同的。同样，如果再做第 \(k\) 次倍增时，得到的 \(rank\) 数组如果已经互不相同了，那么就说明已经找到了最终的 \(rank\) 数组，可以直接退出循环了。
实现方法
要想通过倍增法求出后缀数组有两种排序方法。
快速排序 \(O(n\log ^2n)\)
用快速排序来做倍增法是很直观，有助于初学者更好地理解后缀数组-倍增法的思路，代码也很简单。
Code
[code]#include#define int long long#define N 1000005#define Mod 1000000007#define For(i,j,k) for(long long i=j;i |
