人太蠢了还是不行，看个基数排序看出了脑震荡。
一些规定：
x位后缀：一个字符串去掉前x个字符串得出的字符串
- 后缀排序
后缀数组其实就是把一个字符串的所有后缀排序之后整出来的东西，例如
aabbcca
排序后
aabbcca
abbcca
a
bbcca
bcca
ca
cca
用于实现后缀排序的主要是倍增法，可以在O(nlogn)的时间复杂度内完成基数排序。而倍增算法也就像所有字符串算法的共性那样：利用已经完成计算的信息优化后一步的信息计算。
就实现而言，我们步骤大体如下：
- 记录下所有后缀第一位的位置，作为它们的编号
- 先将所有后缀按照第一位的大小排序
- 把排好序的所有后缀与它编号+i（从1开始）的后缀“综合”一下，快速得出后缀们前2 ^ i次方位的排序。
- 把i * 2，重复第3、4步。
那么，怎么把后缀“综合”一下呢？我们举个。
假设我们已经把字符串acabaad按照第一位的大小排好了序
acabaad abaad aad ad baad cabaad d
设编号为i的字符串Si的排名为rki，那么可知，Si+1为Si的“一位后缀”。若Si与Sj第一位比较出的顺序相同，我们可以借rki+1与rkj+1对比出Si与Sj前两位的顺序，依次类推，若我们知道Si前len位的排序，我们可以借Si+len求出2 * len的排序。这样，逐位比较进行排序的次数就下降了许多次。
考虑到在排序时，我们事实上只是综合了rki与rki+len进行排序，我们事实上有且仅有一些“两位数”rkirki+len要排序，可以选择优秀的基数排序把单次排序复杂度缩减至O(n)。
- 基数排序
这一部分乍一看很简单理解，事实上，要以正确而快速的复杂度实现又是另一码事了。
思想相当简单，对于一个两位数，先将第二位进行桶排，再将桶排后的顺序用第一位桶排就可以保证两位数的排名了。但实现是一件相当有挑战性的事。
- height数组
即lcp(sa[i - 1],sa[i])，height[i]也就是第i个字符串与在它排名前那个字符串的最长公共前缀。
关于height[rk[i]] >= height[rk[i - 1]] - 1的证明：
设位置为i - 1的后缀为s1,在它排名前的一个后缀为s2，设位置为i的后缀为s3，在它排名前的一个后缀为s4。若两字符串首字母不同，则height[rk[i - 1]] = 0，可得结果。
若两字符串首字母相同，则两字符串的一位后缀的先后顺序同这两个字符串的先后顺序一样，也就是说s2的一位后缀在s3前，s2的一位后缀的排名<=s4。可知s4与s3的lcp要大于等于s4与s2的一位后缀的lcp。
而s1的一位后缀与s2的一位后缀的lcp明显是height[rk[i - 1]] - 1，故结果成立。
（证明思想剽窃自自为风月马前卒的博客）
口胡的证明，看不懂正常（我自己也看不懂）。
有了这个，我们就可以从height[rk[i - 1]]快速推出height[rk[i]]，复杂度为O(n)。