最大最大繰返し部分文字列

Question

部分文字列の長さは1,2,3 ... です。解決しようとしていた問題は、最大回数発生した部分文字列を見つけることでした。だから、それは基本的に最大頻度を持つキャラクターを見つけることに踏み切った。 しかし、私はO（n）のサフィックスツリーを使って最も長い繰り返し部分文字列を見つけることができることを発見しました。 しかし、接尾辞ツリーは長さを優先順位として保持する部分文字列を返します。 最も頻繁に発生する部分文字列を探したいと思っていました。例えばのために ：

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. 

私は2つのインデックスiとjの間の部分文字列を生成することにより、この問題を解決しようとしました。その後、O（n）で実行されているZアルゴリズムを使用して、それぞれの場合にこれらの部分文字列の出現を見つける。しかし、総複雑さはO（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); 
     } 
    } 

だった私はそれを効率的に行うための適切な解決策を見つけることができないのです。 助けてください。 ありがとうございます。

Answer 1

単一文字は部分文字列としてカウントされるため、最大反復部分文字列は、文字列内の最も一般的な文字に等しい頻度で発生する必要があります。

最大反復部分文字列内の各文字は、文字列内に1回だけ出現することができます。複数回出現した場合、その文字は最大繰り返し文字列になるためです。たとえば、文字列 "dad"は文字列 "dadxdadydadzdadydad"で5回発生しますが、部分文字列 "d"は10回発生します。

また、毎回同じ順序で表示する必要があります（そうしないと、個々の文字は部分文字列よりも頻度が高くなり、繰り返し部分文字列自体が最大になります）。それらはまた、部分文字列とは別に出現することもできません（または、それらが最大繰返し部分文字列になることもあります）。

したがって、最大繰返し部分文字列は、同様に最も頻繁に発生する文字のサブセット（またはすべて）で構成されている必要があります。

文字列を1つだけ通過させてカウントするだけで、どの文字かを簡単に把握できます。各文字の前後にどの文字が現れるかを追跡し、毎回同じであれば文字を格納し、それ以外の場合はゼロを格納することによって、どの文字がどの順序で出現するかを推測することもできます。たとえば、文字列「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を使用して、文字の頻度と前および次の文字を含む構造体にすることができます。