后缀数组

什么是后缀数组

后缀数组是处理字符串的有力工具 —罗穗骞

个人理解：后缀数组是让人蒙逼的有力工具！

就像上面那位大神所说的，后缀数组可以解决很多关于字符串的问题，

譬如这道题

 

注意：后缀数组并不是一种算法，而是一种思想。

实现它的方法主要有两种：倍增法$O(nlogn)$ 和 DC3法$O(n)$

其中倍增法除了仅仅在时间复杂度上不占优势之外，其他的方面例如编程难度，空间复杂度，常数等都秒杀DC3法

 

我的建议：深入理解倍增法，并能熟练运用（起码8分钟内写出来&&没有错误）。DC3法只做了解，吸取其中的精髓；

 

但是由于本人太辣鸡啦，所以本文只讨论倍增法

 

前置知识

后缀

这个大家应该都懂吧。。

比如说$aabaaaab$

它的后缀为

基数排序

这个我就不讲了（实际是因为我懒。）

不懂的可以看这里

http://blog.csdn.net/lemon_tree12138/article/details/51695211

或者等我哪天心血来潮了补一下

倍增法

首先定义一坨变量

$sa[i]$：排名为$i$的后缀的位置

$rak[i]$：从第$i$个位置开始的后缀的排名

$tp[i]$：基数排序的第二关键字，意义与$sa$一样

$tax[i]$：$i$号元素出现了多少次。辅助基数排序

$s[i]$：字符串

 

可能大家觉得$sa$和$rak$这两个数组比较绕，没关系，多琢磨一下就好

事实上，也正是因为这样，才使得两个数组可以在$O(n)$的时间内互相推出来

具体一点

$rak[sa[i]]=i$

$sa[rak[i]]=i$

 

那我们怎么对所有的后缀进行排序呢？

我们把每个后缀分开来看。

开始时，每个后缀的第一个字母的大小是能确定的，也就是他本身的ASCLL值

具体点？把第$i$个字母看做是$(s[i],i)$的二元组，对其进行基数排序

 

这样我们就得到了他们的在完成第一个字母的排序之后的相对位置关系

 

接下来呢？

不要忘了， 我们算法的名称叫做“倍增法”

 

剩下的内容后天再写。

因为要交作业，所以就提前发出来了。

抱歉