가장 긴 반복되는 부분 문자열

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으로 묘사 된 매우 우아한 (그러나 선형은 아니지만) 구현이 있습니다.