概念 

后缀:从母串的某一位置开始到结尾,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])的最长公共前缀,也就是排名相邻的两个后缀的最长公共前缀。

算法

Ukkonen 算法 O(n)

DC3算法 O(3n)

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

应用

例1:最长公共前缀

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

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

 

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

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