Längste maximale Wiederholungszeichenfolge

Question

Eine Teilzeichenfolge kann die Länge 1,2,3 haben ... Die Frage, die ich zu lösen versuchte, beinhaltete das Auffinden der Teilzeichenfolge, die die maximale Anzahl von Malen aufgetreten ist. Es ist also praktisch nicht möglich, den Charakter mit der maximalen Häufigkeit zu finden. Allerdings habe ich herausgefunden, dass ich die längste sich wiederholende Teilkette mit Suffixbaum in O (n) finden kann. Suffixbaum gibt jedoch den Teilstring zurück, wobei die Länge als Priorität beibehalten wird. Ich wollte den Teilstring finden, der am häufigsten vorkommt, und von diesen Teilstrings möchte ich den längsten finden. Für zB:

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. 

Ich habe versucht, dieses Problem zu lösen, indem Teilkette zwischen zwei Indizes i und j zu erzeugen. Danach findet das Auftreten dieser Teilstrings jeweils unter Verwendung des in O (n) ablaufenden Z-Algorithmus statt. Allerdings ist die Gesamtkomplexität war O (n^3)

My O (n^3) Code

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); 
     } 
    } 

Ich bin nicht in der Lage eine passende Lösung zu finden, um sie effizienter zu machen. Bitte helfen. Danke.

Answer 1

Ein einzelnes Zeichen zählt als Unterzeichenfolge, daher muss die sich wiederholende Höchstzeichenfolge mit einer Häufigkeit auftreten, die dem häufigsten Zeichen in der Zeichenfolge entspricht. Eine Implikation davon ist, dass jedes Zeichen in der sich wiederholenden Höchstzeichenkette nur einmal in der Zeichenkette auftreten kann, denn wenn es mehr als einmal vorkommt, wird diese Zeichenkette zur höchsten sich wiederholenden Zeichenkette. Zum Beispiel tritt der Teilstring "Vater" 5 mal in der Zeichenkette "vadxdadydadzdadydad" auf, aber der Teilstrang "d" tritt 10 mal auf.

Sie müssen auch jedes Mal in der gleichen Reihenfolge erscheinen (sonst hätten die einzelnen Zeichen eine höhere Frequenz als der Teilstring und wären der sich selbst wiederholende Teilstring). Sie können auch nicht separat für die Teilzeichenfolge angezeigt werden (oder sie würden wieder die maximal wiederkehrende Teilzeichenfolge).

Daher muss der sich wiederholende Teilstring aus einer Teilmenge (oder aus allen) der am häufigsten auftretenden Zeichen bestehen.

Wir können leicht herausfinden, welche Zeichen dies sind, indem wir nur einen Durchlauf durch die Zeichenfolge machen und sie zählen. Wir können auch ableiten, welche Zeichen in welcher Reihenfolge erscheinen, indem wir verfolgen, welche Zeichen vor und nach jedem Zeichen erscheinen, und das Zeichen speichern, wenn es jedes Mal dasselbe ist, und sonst Null. Zum Beispiel in der Zeichenfolge „abcxabcyabczabcyabc“, wird das Zeichen „b“ immer mit vorangestelltem „a“, gefolgt von „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; 

Dann können wir über jedes Zeichen und von denen iterieren, die haben eine Frequenz gleich der maximalen Frequenz, die Länge der Zeichenfolge finden wir, indem sie die next Zeichenindizes mit diesem Zeichen beginnen kann Form:

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; 
     } 
    } 
} 

Sobald wir die maximale Wiederholung String gefunden haben, drucken sie es aus:

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

Wenn Sie nicht gerne über diese Arrays mit fester Größe iterieren oder UNICODE-Zeichen usw. unterstützen müssen, können Sie eine map vom Zeichentyp zu einer Struktur verwenden, die die Häufigkeit des Zeichens und die Vor- und Nachzeichen enthält.