javascript 后缀数组

后缀数组是处理字符串的利器, 它本身涉及许多辅助概念.

基本概念

1.1子串

表示字符串的某一小段, 如awbcdewg拥有 awbc， awbcd， awbcde等子串。

1.2后缀

后缀是字符串从某个位置起到达末尾的一种特殊子串。后缀可以等于自身，相等于从一个字符开始. 假令我们设计一个取后缀的函数, 它可以这样实现:

后缀必须包含最后一个字符.

字符串rubylouvre，它的后缀就包含rubylouvre、ubylouvre、bylouvre、 ylouvre、louvre、ouvre，uvre、vre、 re、 e 它们都必须包含最后一个字符e。

1.3 字典排序

字符串默认的比较算法, “aa”

首先从左到右, 各自取得第一个字符, “a"与"a”, 如果相同, 则比较各自的第二个字符. 否则, 比较其charCode值. 如i 和 b比, i的charCode为105, b的charCode为98, b肯定比i小, 那么不用再比较.

如果其中之一是另一个的前缀，则短的那个排前面：aaa 1.4后缀数组

后端数组就是某个字符串的所有后缀按照字典顺序进行排序后得到的位置数组. 如字符串ADCEFD, 当i从0到5递增时,我们通过上面的suffix函数得到其所有 后缀.

index

A

D

C

E

F

D

按字典排序后

index

A

D

C

E

F

D

这个[0,2,5,1,3,4]就是字符串的后缀数组.

倍增算法

上面我们通过非常朴素的方式,逐个取得它的所有后缀,然后通过语言本身的sort方法进行字典排序.这个sort在不同的宿主环境中,内部采取的排序算法都不一样,就是一个黑箱.

整个过程大家可以参考罗穗骞的论文，但由于语言的差异，我看不 懂他在写什么，直接对着它的那张图搞出来了。

但这依赖于原生的sort, 我们可以将sort改成计数排序。

height数组

那么如何计算height？我们定义h[i]=height[rank[i]]，也就是Suffix[i]和它前一名的最长公共前缀，那么很明显有h[i]>=h[i-1]-1。因为h[i-1]是Suffix[i-1]和它前一名的最长公共前缀，设为Suffix[k]，那么Suffix[i]和Suffix[k+1] 的最长公共前缀为h[i-1]-1，所以h[i]至少是h[i-1]-1。所以我们可以按照求h[1],h[2],h[3] 顺序计算所有的height。代码如下

DC3算法

DC3算法(Difference Cover mod 3)是J. Kärkkäinen和P. Sanders在2003年发表的论文 "Simple Linear Work Suffix Array Construction"中描述的线性时间内构造后缀数组的算法。详见下文

http://spencer-carroll.com/th…

太难了，略过。 此外还有其他构造算法，如SA-IS：

https://zhuanlan.zhihu.com/p/…

我应该是搞错学习顺序了，应该先学hash树再学trie树再学压缩树再学后缀树再学后缀自动机。即便我头脑这么好使，跨度这么大，还是碰得一脸灰的。

文章来源网络，如有侵权请联系小编