首页 > 笔记 > 后缀数组算法总结

后缀数组算法总结

后缀数组提供了一种新思想——倍增和字符串的有趣结合

先来接触一些基础定义

子串:就是字符串的一部分,必须连续。
后缀:是一种子串,它的结尾必须为字符串的最后。
大小比较:就是字典序比较,从头开始比,不相同的话字典序大的那个大,假如相同就向后移动。假如移到其中一个串的结尾还相同的话,长的那个大。
后缀数组:把所有的后缀编号,排序后把编号存在这个数组里。
名次数组:存的是每个后缀的名次

求sa有很多的方法,比较常用的是倍增法,能在\(O(n \log n)\)的时间里求出sa。其实还有很多方法,但是比较难实现。

 

我们使用的例子是“aabaaaab”它的结果如图所示:

images

我们先把它的所有后缀都列出来:

images

如何排序呢,最好想的就是万能的sort。但是效率太低了,是\(O(n^2 \log n)\)的,别忘了比较两个字符串也是\(O(n)\)的。

这样的话我们就需要用到某种\(O(n)\)的排序类型了。于是我们想到了计数排序

何为计数排序呢,

一般的排序都需要比较其中元素的值,这种排序的复杂度下限就是\(O(n \log n)\),算导上有证明,但是计数排序不需要比较,假如输入一个数X,我们可以确定小于X的元素的个数,这样,就可以把这个数放在输出数组的指定位置上。

步骤:

1、初始化辅助数组c[i]。

2、遍历每一个输入元素,如果一个输入元素为i,则辅助数组中相应的c[i]的值加1。执行完毕之后。数组c中存储的就是各个键值在输入数组中出现的次数。

3、再计算一下前缀和,我们就知道了小于每个数的个数了。

4、将a[i]放到它在输出数组的正确位置上。对于一个值来说,c[a[i]]的值就是它在输出数组中的正确位置。在做这步的时候,把c[i]减1,这样就能处理相同值的情况了。

计数排序的时间复杂度就为\(O(n)\)了。可这有什么用呢,我们是字典序排序。

这时候,我们就可以使用倍增。因为倍增的话,每次的关键字长度都会变成它原来的两倍,而在后缀中,满足在同一个字符串中的性质,它其中有很多重叠的部分。实际上,我们可以把倍增出来的关键字变成两份,一份是上次关键字排序出来的数组,因为有重复的元素,所以对于另一半来说,它们一定是上一次排出来序的字符串的某个后缀!因为上一次已经让关键字有序了,所以我们直接把上一次排序的数组后移就可以了!前面留空的就是长度不到关键字长度的串,直接按它们的长度摆上就行了。

现在我们就得到了\(O( n \log n)\)的算法了。

接下来我们一点一点地解释一下关于怎么实现的问题:

这里,

n表示字符串的长度
c是上文所述的辅助数组
x表示rank数组,下标表示关键字的位置,值表示关键字大小(rank),相同的值有相同的rank。初始化为字符串s的每个字符大小(此时x并不代表rank,只借助其值比较相对大小)。在每次迭代后,根据sa重新赋值,并代表rank。其实,我觉得可以这么理解,x存的是每个后缀的前缀的种类。因为一开始前缀的长度为1,所以它存的就是s每个字符的大小。以后将每个前缀有序编号了以后这里存的就是字符串的编号。
y表示排序后的第二关键字数组,下标表示名次,值代表第二关键字的首字符位置。
sa构造完成前表示关键字数组,下标表示名次,值表示关键字的首字符位置,值相同的时候名次根据在原串中相对位置的先后决定;构造完成后表示后缀数组,下标表示名次,值表示后缀的首字符位置。

我们先看一下第一段代码

这其实就是对每个后缀的第一位进行一下计数排序。唯一需要注意的一点就是最后一个for是从n-1开始循环。这样的话字符串位置相对靠前的后缀就会先出现

排序完是这样的

images

然后

k表示关键字的长度

这里只用了两行语句就完成了对第二关键字的排序

注意因为直接后移上次排序的数组,所以下标需要减k。

第一次排完是这样的

images

然后就是一些非常神的操作了

这部分代码的作用就是用结合两个关键字把总的排序搞出来

我们应该做的,就是先根据第一关键字排序,第一关键字相等时根据第二关键字大小排序。

但是看上去,只进行了一次计数排序啊。

还记得这个计数排序的特点:先根据x的值排序,x值相等时根据出现先后次序排序。

x里面存了上次关键字的排序,在本次排序中即是第一关键字的排序,x的值排序==第一关键字排序这里的计数排序做的是对的。那么第二关键字呢?

前面对第二关键字进行了排序,在这里x[y[i]]就是根据第二关键字的顺序重新改变了第一关键字的顺序,也就是说在本次计数排序中,出现先后次序排序==第二关键字大小排序。

换句话说,我们先单独对第二关键字排序,根据这个顺序改变第一关键字的顺序,由于在计数排序时首先按照第一关键字的值排序,而第一关键字的值没有改变所以首先还是根据第一关键字排序,改变的是第一关键字相同的时候,出现在前面的第二关键字排在前面。

images

做到这里就完成了第一第二关键字的合并,得到了合并以后的关键字顺序,它可以用于下次迭代。

每次新的迭代要用到rank数组x,由于有了刚求的关键字排序数组sa,要得到rank数组也很容易。但是对于相同的值,rank应该相同,所以要判断一下合并以后的关键字是否相同。

这里给出后几次的供参考

 

images

images

images

images

完整版

能够线性计算height[]的值的关键在于h[](height[rank[]])的性质,即h[i]>=h[i-1]-1,下面具体分析一下这个不等式的由来。

我们先把要证什么放在这:对于第i个后缀,设j=sa[rank[i] – 1],也就是说j是i的按排名来的上一个字符串,按定义来i和j的最长公共前缀就是height[rank[i]],我们现在就是想知道height[rank[i]]至少是多少,而我们要证明的就是至少是height[rank[i-1]]-1。

好啦,现在开始证吧。

首先我们不妨设第i-1个字符串(这里以及后面指的“第?个字符串”不是按字典序排名来的,是按照首字符在字符串中的位置来的)按字典序排名来的前面的那个字符串是第k个字符串,注意k不一定是i-2,因为第k个字符串是按字典序排名来的i-1前面那个,并不是指在原字符串中位置在i-1前面的那个第i-2个字符串。

这时,依据height[]的定义,第k个字符串和第i-1个字符串的公共前缀自然是height[rank[i-1]],现在先讨论一下第k+1个字符串和第i个字符串的关系。

第一种情况,第k个字符串和第i-1个字符串的首字符不同,那么第k+1个字符串的排名既可能在i的前面,也可能在i的后面,但没有关系,因为height[rank[i-1]]就是0了呀,那么无论height[rank[i]]是多少都会有height[rank[i]]>=height[rank[i-1]]-1,也就是h[i]>=h[i-1]-1。

第二种情况,第k个字符串和第i-1个字符串的首字符相同,那么由于第k+1个字符串就是第k个字符串去掉首字符得到的,第i个字符串也是第i-1个字符串去掉首字符得到的,那么显然第k+1个字符串要排在第i个字符串前面,要么就产生矛盾了。同时,第k个字符串和第i-1个字符串的最长公共前缀是height[rank[i-1]],那么自然第k+1个字符串和第i个字符串的最长公共前缀就是height[rank[i-1]]-1。

到此为止,第二种情况的证明还没有完,我们可以试想一下,对于比第i个字符串的字典序排名更靠前的那些字符串,谁和第i个字符串的相似度最高(这里说的相似度是指最长公共前缀的长度)?显然是排名紧邻第i个字符串的那个字符串了呀,即sa[rank[i]-1]。也就是说sa[rank[i]]和sa[rank[i]-1]的最长公共前缀至少是height[rank[i-1]]-1,那么就有height[rank[i]]>=height[rank[i-1]]-1,也即h[i]>=h[i-1]-1。

证明完这些之后,下面的代码也就比较容易看懂了。

计算每个字符串的字典序排名

 

上一次的计算结果是k,首先判断一下如果k是0的话,那么k就不用动了,从首字符开始看第i个字符串和第j个字符串前面有多少是相同的,如果k不为0,按我们前面证明的,最长公共前缀的长度至少是k-1,于是从首字符后面k-1个字符开始检查起即可。

将计算出来的height[rank[i]]的值,也就是k,赋给height[rank[i]]。i是由0循环到n-1,但实际上height[]计算的顺序是由height[rank[0]]计算到height[rank[n-1]]。

总代码

应用啥的下次讲吧。

 


1 COMMENT

  1. 一个蒟蒻小学弟2018-02-27 上午10:50

    学长你证明h[i]>=h[i-1]-1的过程真心精彩,能转载一下吗?

如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×