首页 > 代码库 > 后缀数组求解字符串的最长重复子串

后缀数组求解字符串的最长重复子串

后缀数组

给定一个字符串,求出其最长的重复子串。

思路:使用后缀数组,对一个字符串生成相应的后缀数组后,然后再排序,排完序依次检测相邻的两个字符串的开头公共部分。
这样的时间复杂度为:

生成后缀数组 O(N)
排序 O(NlogN*N) 最后面的 N 是因为字符串比较也是 O(N)
依次检测相邻的两个字符串 O(N * N)
总的时间复杂度是 O(N^2*logN), 

 

后缀数组求解字符串的最长重复子串