最長重複子字符串更好的複雜性

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。