后缀数组模板题

后缀数组 suffix array是个什么玩意？

回答： 这是用来代替suffix tree的一个辅助的数据结构，按照字典序保存了一个字符串中的所有后缀。相比suffix tree, 据说实现起来更加简单，算法的常数因子小，且更容易充分利用cache locality，提高计算效率。

以题目中的$Str=ababa$为例，字符串$Str$的所有后缀为为

（uoj博客的表格是不是有问题=。=）

排序之后得到

所以最后我们要求的后缀数组就是 $[5,3,1,4,2]$

那么，如何才能得到suffix array呢？

最简单的就是整理出所有的后缀，然后排个序，这不是就搞定了？

然而算算复杂度。。。 排序的复杂度是 $O(nlogn)$，而每次比较字符串又需要花费 $O(n)$时间，所以总的复杂度是 $O(n^2 logn)$。后缀数组可是要应用到拥有天文数字长度的DNA检测中的，算法的复杂度显得至关重要。

幸运的是，计算机专家们已经找到了线性时间的算法，其中有DC3算法和KA算法，主要思想是利用每个后缀之间的关联，帮助进行后缀数组的排序。

更值得关注的是，目前后缀数组最快的、最实用的、（最适合OJ的）算法，SA-IS算法，是由我们中国人提出的，论文链接：农革 后缀数组。作者基于KA算法进行了改进，采用了“Almost Pure Induced-Sorting",就是说把原来KA算法中没有用 induced sort的部分也用这个诱导排序来实现，意外的发现效果惊人。

有时间贴个代码，并讲讲诱导排序。

所谓的诱导排序，就是利用一些威逼利诱的方法来进行排序，无需再重复的一次次扫面子字符串。 还是以 $Str=ababa$ 为例，首先我们在末尾添加一个无效的字符 \$ 当做结束标记，并且规定这个无效字符在排序上小于 $Str$ 中任何可能出现的字符。 原字符串为

1 2 3 4 5 6

a b a b a $

接下来，从右往左对标记每个字符的类型：如果 $Str[i]<Str[i+1]$，那么就标记字符为$S$类型（$type[i]=S$）；如果$Str[i]>Str[i+1]$,那么就标记字符为$L$类型（$type[i]=L$）;若两者相等，那么该字符的类型和右侧字符一样（$type[i]=type[i+1]$）

1 2 3 4 5 6

a b a b a $

S L S L L S

那么，有什么好处呢？

算法认为， 如果 $type[i]== L$并且 $type[i+1]==S$,那么第 $i+1$ 个字符为可疑分子，先把他标个*号 (3 和 6）

1 2 3 4 5 6

a b a b a $

S L S L L S

      *       *

此外，算法会建三个桶（bucket），这是因为字符串中只出现了 $a$和 $b$，以及 \$, 各自建一个桶。目前有一点很清楚，后缀数组中以 $a$ 开头的子串肯定是排在以 $b$ 开头的子串前面。 而 \\$ 符号最小，放在最前面。这样6的位置的是确定的。 至于3， 先把他放到 $a$ 桶的最后。

{\$}{   a   }{ b }

{6}{x x 3}{x x}

{6}{5 x 3}{x x}

{6}{5 x 3}{4 x}

{6}{5 x 3}{4 2}

{6}{5 x 1}{4 2}

{6}{5 3 1}{4 2}

上面接下来几列就是诱导的过程。从左到右：6诱导5，5诱导4，3诱导2， 诱导出的位置放在桶内剩余的最靠左的位置。 到达右端之后再从右往左进行诱导, 2诱导1,4诱导3, 诱导出的位置放在桶内剩余的最靠右的位置。这样整个得到一个初步的后缀数组。

目前的后缀数组已经是正确的了。但是其实面对复杂的字符串，还需要在确定*字符后再继续重复如上的过程。有时候还需要递归。这里就不赘述了。见代码即可。