string - 最长重复子串 更好的复杂性

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. 每对连续后缀的最长公共(public)前缀可以在线性时间内构造后缀数组时计算出来(但 O(n log n) 算法要容易得多)。查阅 this 的引用资料.

3. 如果你真的坚持在线性时间内运行整个东西，那么你可以在线性时间内构造后缀数组。我敢肯定，如果您四处搜索一下，就可以轻松找到指示。

4. 描述了非常优雅(但不是线性)的实现 here .