最长重复子串查找算法

在一个字符串里查找最长的重复子串,比如串”ababa”的最长的重复子串是”aba”,”aba”在”ababa”中重复了2次,且在所有重复子串里是最长的(”ab”虽然也出现了2次,但没有”aba”长)

这个问题最常见算法是用动态规划算法,用公共重复子串算法来解决。但本文介绍的是一种基于后缀子串排序的方法:首先,写出”ababa”的所有后缀子串:

a
ba
aba
baba
ababa

然后按ASCII码大小顺序,将以上所有字符串从小到大排序:

a
aba
ababa
ba
baba

此时,原字符串中所有重复子串,在已经排序过的后缀子串中一定存在于相邻两个后缀子串中,遍历一遍找出最大的重复对即可。在本例中,”aba”就存在与相邻的两个后缀子串”aba”和”ababa”中。

考虑算法复杂度,设原字符串长度N,后缀子串也有N个,若使用快速排序,需要进行O(N*logN)级别的字符串比较,考虑到后缀子串的平均长度为N/2,字符串比较的复杂度为O(N),排序的平均复杂度为:

O(N^2*logN)

这就是该算法的平均复杂度。后续的“在相邻后缀子串中寻找最长重复子串”的操作的复杂度显然是O(N^2),相比排序的复杂度可以忽略。

相比暴力算法(二重遍历字符串,寻找一对最长重复子串)的O(N^3)的复杂度,这种算法优雅地提升了效率。

C语言实现该算法不需要真正地为N个后缀子串分配空间。因为C有指针,只需要建立一个N长度的指针数组,将指针数组的每个指针指向原字符串的每个字符,它正好就是一个后缀子串。然后对指针数组排序,原字符串也不会受到破坏。