编写中，待完善。。。
前置知识 : 后缀(???),基数排序(说通俗一点就是桶子排序)，基础倍增。
后缀数组是一种处理字符串问题的利器，可以起到代替后缀树的作用，在码量上具有绝对的优势。正常情况下，大家都会使用后缀数组而非后缀树。虽然后缀数组十分的好写，但是过程难以令人理解。今天我会使用尽量通俗的语言帮助大家理解什么是后缀数组，以及相关的拓展。
在开始之前
我们需要对于一些变量进行定义（别的数字在后边讲到）：
\(sa_i\) 表示排名为 \(i\) 的后缀下标是多少。
\(rk_i\) 表示下标 \(i\) 的后缀的排名是多少。
那么这两个数组是具有性质： \(sa[rk_i]=rk[sa_i]=i\) 。这一点看起来比较的绕，但是还是稍加思考可以理解的。也就是说，我们知道了 \(sa\) 和 \(rk\) 中的一者，就可以在线性的时间内推出另一个。
后缀排序
现在进行了定义，该如何求出这个后缀数组呢？我们讲如下两种方法（最最最最牛逼但是常数和码量极大的 \(\text{DC3}\) 我们暂不讨论）：
字符串哈希算法
这个算法的时间复杂度是 \(O(n \log^2 n)\) 。因为相比其他解法较劣势的时间复杂度，并不是很常使用。
相比大家知道怎么编写 \(std::sort\) 的自定义比较函数吧。如果这个比较的时间是 \(O(T)\) 的，那么我们的排序时间就可以做到 \(O(Tn \log n)\) 。那么现在我们的目标就是在尽量块的时间内比较两个后缀的字典序。
最简单的做法就是暴力的枚举，但是注意到 \(LCP\) (最长公共前缀) 是可以二分的，所以我们可以去二分第一个不一样的前缀，比较最后一个字符的大小就可以了。问题就又变换为了如何去比较两个字符串相同，这个显然使用字符串哈希可以在 \(O(1)\) 的时间内解决。那么我们的比较时间就从 \(O(n)\) 优化到了 \(O(n\log n)\) 。
最终的时间复杂度就是 \(O(n \log^2 n)\) 。
标签：log,后缀,时间,数组,sa,rk,浅谈 From： https://www.cnblogs.com/Diavolo/p/17672933.html