相关疑难解决方法(0)

解决这个问题的最佳方法(性能方面)是什么？我被建议使用后缀树.这是最好的方法吗？

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

#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 …