最長最大重複子

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. 

我試圖用兩個指數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

單個字符算作一個子串，因此，因此最大重複子串必須以等於該串中最常見的字符的頻率發生。那

一個含義是，在最大重複子串每個角色只能在字符串中出現一次，因爲如果它發生了多起一次，然後該字符在它自己會成爲最大的重複字符串。例如，字符串「dad」在字符串「dadxdadydadzdadydad」中出現5次，但子字符串「d」出現10次。

它們還具有每次（或者單個字符將具有比所述子更高的頻率，併成爲最大重複子串本身）以相同的順序出現。它們也不能單獨出現在子字符串中（否則它們會成爲最大重複子字符串）。

因此，最大重複子串必須進行的同樣最頻繁出現的字符的子集（或全部）組成。

我們可以很容易地找出哪些字符只是通過一次穿過字符串並對它們進行計數。我們還可以通過跟蹤每個字符前後出現哪些字符，如果每次都是相同的字符來存儲字符，則可以推斷出哪些字符以哪種順序出現，否則爲零。例如，在字符串「abcxabcyabczabcyabc」，字符「B」總是由「A」和後面的「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從字符類型包含字符的出現頻率和prev和下一個字符的結構。