后缀数组
一些约定
字符串下标从 0 开始。
后缀 i 表示以下标 i 的字符开始的后缀。
基本概念
后缀数组（Suffix Array）主要是两个数组：sa 和 rk。
其中，sa 为所有后缀按字符串序的升序排列，rk[i] 表示后缀 i 在 sa 中的下标。
生成方法
朴素 O(n^2 \log n) 做法
基于字符串比较的朴素排序实现，其中比价两个字符串的时间是 O(n) 的，故排序总时间是 O(n^2 \log n)。
基于倍增的 O(n \log^2 n) 做法
一句话：倍增子串的长度上限，维护名次数组 rk，直到长度上限达到 n。
该过程进行 \log n 次排序，每次排序的时间复杂度为 O(n \log n)。
-
初始长度上限为 1，对每个字符进行排序，得到名词数组 rk_1。
-
假设我们已经知道了长度上限为 w 的子串排名 rk_w，则二元组序列 p[i] = (rk_w[i], rk_w[i + w]) 排序得到的名词数组即为长度上限为 2w 的子串排名 rk_{2w}。
注：若第二关键字不存在（i + w 越界）则取 -1 即可。 -
循环执行上一步直到长度上限大于等于原字符串长度 n。
引入基数排序和计数排序优化到 O(n \log n)
在基于倍增的 O(n \log^2 n) 做法中，单次排序的复杂度为 O(n \log n)。如果能 O(n) 排序，就能将总复杂度优化到 O(n \log n)。
由于单次排序的过程中关键字是排名，值域为 O(n)，并且是一个双关键字排序，可以使用基数排序优化至 O(n)。