最长最大重复子

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和下一个字符的结构。