가장 긴 최대 반복 부분 문자열

Question

부분 문자열의 길이는 1,2,3 ... 입니다. 해결하기 위해 시도한 질문에는 최대 횟수가 발생한 부분 문자열을 찾는 것이 포함되었습니다. 그래서 그것은 기본적으로 최대 빈도를 가진 캐릭터를 찾는데 실패했습니다. 그러나 O (n)에서 접미어 트리를 사용하여 가장 긴 반복 부분 문자열을 찾을 수 있다는 것을 알았습니다. 그러나 suffix tree는 길이를 우선 순위로 유지하면서 하위 문자열을 반환합니다. 가장 많은 횟수로 발생하는 하위 문자열을 찾고 싶었고 하위 문자열 중에서 가장 긴 문자열을 찾고 싶습니다. 예를 들어 는 :

In the following string: ABCZLMNABCZLMNABC 
A suffix tree will return ABCZLMN as the longest repeating substring. 
However, what I am looking for is ABC; as it is the longest out of all the ones having frequency = 3. 

I 두 지수 I와 J 사이의 문자열을 생성함으로써,이 문제를 해결하려고. 그 후 O (n)에서 실행되는 Z 알고리즘을 사용하여 각 부분 문자열의 발생을 찾습니다. 그러나 전체 복잡성은 내가 그것을 효율적으로 만들 수있는 적합한 솔루션을 찾을 수 없습니다입니다 (N^3)

내 O (N^3) 코드

map<ll,vector<string>> m; 
    string s; cin >> s; 
    for(ll i=0;i<s.length();i++){ 
     string c; 
     for(ll len=0; i+len<s.length();len++){ 
      c+=s[i+len]; 
      ll z[N]; 
      ll l=0,r=0; 
      string kk; 
      for(ll p=0;p<c.length();p++){ 
       kk+=c[p]; 
      } 
      kk+="#"; 
      for(ll p=0;p<s.length();p++){ 
       kk+=s[p]; 
      } 
      for(ll k=1;k<kk.length();k++){ 
       if(k>r){ 
        l=r=k; 
        while(r<c.length()&&kk[r-l]==kk[r])r++; 
        z[k]=r-l; 
        r--; 
       } 
       else{ 
        ll m=k-l; 
        if(z[m]<r-k+l)z[k]=z[m]; 
        else{ 
         l=k; 
         while(r<c.length()&&kk[r-l]==kk[r])r++; 
         z[k]=r-l; 
         r--; 
        } 
       } 
      } 
      ll occ=0; 
      for(ll n=0;n<kk.length();n++){ 
       if(z[n]==c.length())occ++; 
      } 
      m[occ].push_back(c); 
     } 
    } 

O했다. 친절히 도와주세요. 감사합니다.

Answer 1

단일 문자는 하위 문자열로 계산되므로 최대 반복 하위 문자열은 문자열의 가장 일반적인 문자와 동일한 빈도로 발생해야합니다.

하나의 의미는 최대 반복 부분 문자열의 각 문자는 문자열에서 한 번만 나타날 수 있습니다. 두 번 이상 발생하면 해당 문자가 최대 반복 문자열이되기 때문입니다. 예를 들어 "dad"라는 하위 문자열은 문자열 "dadxdadydadzdadydad"에서 5 번 발생하지만 하위 문자열 "d"는 10 번 발생합니다.

매번 같은 순서로 나타나야합니다. 그렇지 않으면 개별 문자가 하위 문자열보다 빈도가 높고 최대 반복 하위 문자열 자체가됩니다. 또한 하위 문자열에 개별적으로 표시 될 수 없으며 (또는 반복되는 하위 문자열이 최대 반복 부분이 될 수도 있습니다).

따라서 최대 반복 하위 문자열은 가장 자주 발생하는 문자의 하위 집합 (또는 모두)으로 구성되어야합니다.

문자열을 통과시켜 계산하는 것만으로 쉽게 알 수 있습니다. 각 문자의 앞뒤에 나타나는 문자를 추적하고, 매번 동일한 경우 문자를 저장하고, 그렇지 않은 경우 0을 저장함으로써 어떤 문자가 어떤 순서로 나타나는지 추론 할 수 있습니다. 예를 들어, 문자열 "abcxabcyabczabcyabc"에 문자 "B는"항상 "는이"와 "C"다음 앞에는 :

string s; cin >> s; 
int i, freq[256]; 
char prev[256], next[256]; 
for(i = 1; i < 256; i++) 
    freq[i] = prev[i] = next[i] = 0; 
int maxFreq = 0; 
for(i = 0; i < s.length(); i++) 
{ 
    char c = s[i]; 
    char p = (i == 0) ? 0 : s[i-1]; 
    char n = (i < s.length() - 1) ? s[i+1] : 0; 
    if(freq[c] == 0) // first time to encounter this character 
    { 
     prev[c] = p; 
     next[c] = n; 
    } 
    else // check if it is always preceded and followed by the same characters: 
    { 
     if(prev[c] != p) 
      prev[c] = 0; 
     if(next[c] != n) 
      next[c] = 0; 
    } 
    // increment frequency and track the maximum: 
    if(++freq[c] > maxFreq) 
     maxFreq = freq[c]; 
} 

if(maxFreq == 0) 
    return 0; 

다음, 우리는 각 문자를 통해하고있는 것들의 반복 할 수 최대 주파수와 동일한 주파수, 우리는 next 문자 인덱스에 따라이 문자로 시작 형성 할 수있는 문자열의 길이 찾을 : 우리가 최대 반복 문자열을 발견하면

int maxLen = 0; 
int startingChar = 0; 
for(i = 1; i < 256; i++) 
{ 
    // should have a frequency equal to the max and not be preceded 
    // by the same character each time (or it is in the middle of the string) 
    if((freq[i] == maxFreq) && (prev[i] == 0)) 
    { 
     int len = 1, j = i; 
     while(next[j] != 0) 
     { 
      len++; 
      j = next[j]; 
     } 
     if(len > maxLen) 
     { 
      maxLen = len; 
      startingChar = i; 
     } 
    } 
} 

을, 그것을 밖으로 인쇄 :

// print out the maximum length string: 
int j = startingChar; 
while(j != 0) 
{ 
    cout << (char)j; 
    j = next[j]; 
} 
cout << endl; 

고정 크기 배열을 반복하거나 UNICODE 문자 등을 지원해야하는 경우에는 문자 유형에서 문자의 빈도와 이전 및 다음 문자가 들어있는 구조체에 map을 사용할 수 있습니다.