后缀数组
概念
后缀:从母串的某一位置开始到结尾,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