最长重复子字符串更好的复杂性

Question

我已经通过比较排序后缀列表后字符串的后缀来实现解决方案。有没有比这段代码更好的线性时间算法？

#include <iostream> 
#include <cstring> 
#include <algorithm> 
using namespace std; 
void preCompute(string input[],string s) 
{ 
    int n = s.length(); 
    for(int i=0; i<n; i++) 
     input[i] = s.substr(i,n); 
} 
string LongestCommonSubString(string first,string second) 
{ 
    int n = min(first.length(),second.length()); 
    for(int i=0; i<n; i++) 
     if(first[i]!=second[i]) 
      return first.substr(0,i); 
    return first.substr(0,n); 
} 
string lrs(string s) 
{ 
    int n = s.length(); 
    string input[n]; 
    preCompute(input,s); 
    sort(input, input+n); 
    string lrs = ""; 
    for(int i=0; i<n-1; i++) 
    { 
     string x = LongestCommonSubString(input[i],input[i+1]); 
     if(x.length()>lrs.length()) 
     { 
      lrs = x; 
     } 
    } 
    return lrs; 
} 
int main() 
{ 
    string input[2] = {"banana","missisipi"}; 
    for(int i=0;i<2;i++) 
     cout<<lrs(input[i])<<endl; 
    return 0; 
} 

我发现这个问题非常好的资源。请参阅here

Answer 1

您可以在线性时间内构建后缀树（请参阅this）。最长的重复子字符串对应于最深的内部节点（当我说最深的时候，我的意思是来自根的路径具有最大数量的字符，而不是最大数量的边缘）。原因很简单。内部节点对应于多个后缀中出现的后缀（即子字符串）的前缀。

实际上，这是相当复杂的。所以你采取的方法是足够好的。我可以建议一些修改：

1. 不要创建子字符串，子字符串可以用一对数字表示。当你需要实际的字符时，查找原始字符串。实际上，后缀对应于单个索引（起始索引）。

2. 可以在线性时间构造后缀数组时计算每对连续后缀中最长的公共前缀（但O（n log n）算法更容易）。请参阅this的参考资料。

3. 如果你真的坚持在线性时间内运行整个事情，那么你可以在线性时间构造后缀数组。我相信，如果你搜索一下，你可以很容易地找到指针。

4. 有非常优雅的（但不是线性的）实现描述here。