1.摘要

后缀数组是后缀树的一个非常精巧的替代品，它比后缀树容易编程实现，能够实现后缀树的很多功能而时间复杂度也不太逊色，并且，它比后缀树所占用的空间小很多。在实际应用中，后缀数组经常用于解决字符串有关的复杂问题。

2. 概念 

后缀：从母串的某一位置开始到结尾，suffix(i) = Ai,Ai+1…An。

后缀数组：后缀数组SA是个一维数组，它保存1…n的某个排列SA[1],SA[2]…SA[n]，并且保证suffix(SA[i])< suffix(sa[i+1])，也就是将s的n个后缀从小到大排好序后的开头位置保存到sa中。

名次数组：名次数组Rank[i]保存的是以i开头的后缀的排名，与SA互为逆。简单的说，后缀数组是“排在第几的是谁”，名次数组是“你排第几”。

height数组，height[i] = suffix(SA[i-1])和suffix(SA[i])的最长公共前缀，也就是排名相邻的两个后缀的最长公共前缀。

3. 算法

Ukkonen 算法 O(n)

DC3算法 O(3n)

倍增算法 O(nlogn)，实现简单。

4. 应用

例1：最长公共前缀

    给定一个串，求任意两个后缀的最长公共前缀。

解：先根据rank确定这两个后缀的排名i和j(i<j)，在height数组i+1和j之间寻找最小值。(可以用rmq优化)

 

例2：最长重复子串(不重叠)(poj1743)

解：二分长度，根据长度len分组，若某组里SA的最大值与最小值的差>=len，则说明存在长度为len的不重叠的重复子串。

 

例3：最长重复子串(可重叠)

解：height数组里的最大值。这个问题等价于求两个后缀之间的最长公共前缀。

 

例4：至少重复k次的最长子串(可重叠)(poj3261)

解：二分长度，根据长度len分组，若某组里的个数>=k，则说明存在长度为len的至少重复k次子串。

 

例5：最长回文子串(ural1297)

    给定一个串，对于它的某个子串，正过来写和反过来写一样，称为回文子串。

解：枚举每一位，计算以这个位为中心的的最长回文子串(注意串长要分奇数和偶数考虑)。将整个字符串反转写在原字符串后面，中间用$分隔。这样把问题转化为求某两个后缀的最长公共前缀。

 

例6：最长公共子串(poj2774)

    给定两个字符串s1和s2，求出s1和s2的最长公共子串。

解：将s2连接到s1后，中间用$分隔开。这样就转化为求两个后缀的最长公共前缀，注意不是height里的最大值，是要满足sa[i-1]和sa[i]不能同时属于s1或者s2。

 

例7：长度不小于k的公共子串的个数(poj3415)

    给定两个字符串s1和s2，求出s1和s2的长度不小于k的公共子串的个数(可以相同)。

解：将两个字符串连接，中间用$分隔开。扫描一遍，每遇到一个s2的后缀就统计与前面的s1的后缀能产生多少个长度不小于k的公共子串，这里s1的后缀需要用单调栈来维护。然后对s1也这样做一次。

 

例8：至少出现在k个串中的最长子串(poj3294)

    给定n个字符串，求至少出现在n个串中k个的最长子串。

将n个字符串连接起来，中间用$分隔开。二分长度，根据长度len分组，判断每组的后缀是否出现在不小于k个原串中。

5. 参考

http://yzmduncan.iteye.com/blog/979771
http://dongxicheng.org/structure/suffix-array/
​http://www.newsmth.net/bbsanc.php?path=%2Fgroups%2Fcomp.faq%2FAlgorithm%2FNetResources%2FM.1190776063.E0&ap=460
​http://gaterking.blog.51cto.com/69893/340602