后缀数组之倍增算法——学习笔记

什么是后缀：一个字符串从某位开始到其末尾的子串。 什么是后缀数组：一个字符的所有后缀从小到大排列所形成的的数组。 后缀数组可以解决很多的字符串问题，本文主要写的是构造后缀数组的倍增算法。 暴力构造：直接把n个后缀排序。因为比较字符串需要O(n)$O(n)$的时间，所以总复杂度O(n2log2n)$O(n^2log_2n)$。 这样完全没有利用到n个元素都是某一字符串的后缀这个特性，如何改进呢？ 倍增算法的思想就是比较所有后缀的前缀，并倍增增加当前考察的前缀长度。 具体来说： 假设我们已经对所有后缀只取前k位并排好序，现在我们要把长度增加到k*2。可以发现对于一个后缀i (s[i~n])，他的前k*2位可以分成两部分： 后缀i的前k位 与 后缀i+k的前k位。 考虑比较两个长度同为k*2的字符串：若前k位大小不同就能直接出结果，否则就比较后k位的大小。 这些前缀的排名在之前已经得到了，我们把后缀i的前k位作为第一关键字，后缀i+k的前k位作为第二关键字，这样是不是就可以比较大小了呢？ 结合下面这张图会好理解一些：(盗来的) 因为关键字其实就是上一次的排名，范围只有1~N,所以我们可以用基数排序的方法O(n)得出当前答案。这样总复杂度为O(nlog2n)$O(nlog_2n)$，很优秀。 下面是我的模板，相比dalao们的繁琐一点，常数大一些，但是可读性还是很强的，不容易写错。