Minimale zyklische Shift-Algorithmus Erklärung

Question

Ich bin vor kurzem auf diesen Code gestoßen ohne Kommentar. Es findet eine minimale zyklische Verschiebung des Wortes (dieser Code gibt speziell seinen Index in der Zeichenkette zurück) und seinen sogenannten Duval-Algorithmus. Nur info Ich fand, beschreibt Algorithmus in wenigen Worten und hat saubereren Code. Ich würde jede Hilfe beim Verständnis dieses Algorithmus schätzen. Ich fand Textalgorithmen immer ziemlich schwierig und ziemlich schwer zu verstehen.

int minLexCyc(const char *x) { 
    int i = 0, j = 1, k = 1, p = 1, a, b, l = strlen(x); 
    while(j+k <= (l<<1)) { 
     if ((a=x[(i+k-1)%l])>(b=x[(j+k-1)%l])) { 
      i=j++; 
      k=p=1; 
     } else if (a<b) { 
      j+=k; 
      k=1; 
      p=j-i; 
     } else if (a==b && k!=p) { 
      k++; 
     } else { 
      j+=p; 
      k=1; 
     } 
    } 
    return i; 
} 

Answer 1

Zuerst glaube ich, dass Ihr Code einen Fehler enthält. Die letzte Zeile sollte return p; sein. Ich glaube, dass ich den Index der lexikographisch kleinsten zyklischen Verschiebung halte und p die kleinste Verschiebung hält, die übereinstimmt. Ich denke auch, dass dein Stoppzustand zu schwach ist, d. H. Du tust zu viel nach, nachdem du ein Spiel gefunden hast, aber ich bin mir nicht sicher, was genau es sein sollte.

Beachten Sie, dass ich und j nur weiterkommen und dass ich immer kleiner als j bin. Wir suchen nach einer Zeichenfolge, die mit der Zeichenfolge übereinstimmt, die bei i beginnt, und wir versuchen, sie mit einer Zeichenfolge abzugleichen, die bei j beginnt. Wir tun dies, indem wir das k-te Zeichen jeder Zeichenkette vergleichen, während wir k erhöhen (solange sie übereinstimmen). Beachten Sie, dass wir nur i ändern, wenn wir feststellen, dass die Zeichenfolge, die bei j beginnt, lexikographisch kleiner ist als die Zeichenfolge, die bei j beginnt, und dann setzen wir i auf j und setzen k und p auf ihre Anfangswerte zurück.

Ich habe keine Zeit für eine detaillierte Analyse, aber es sieht aus wie

1. i den Beginn des lexicographic kleinsten zyklischen Verschiebung =
2. j = Beginn der zyklischen Verschiebung wir gegen die passen verschieben ab i
3. k = das Zeichen in Zeichenfolgen i und j gerade betrachtet (die Strings Spiel in den Positionen 1 bis k-1
4. p = die zyklische Verschiebung unter Berücksichtigung (i glauben, p steht für prefix)

bearbeiten geht weiter

Codeabschnitt

if ((a=x[(i+k-1)%l])>(b=x[(j+k-1)%l])) { 
     i=j++; 
     k=p=1; 

Verschiebt den Anfang des Vergleichs zu einer lexikographisch früheren Zeichenfolge, wenn wir einen finden und neu initialisiert alles andere.

dieser Abschnitt

} else if (a<b) { 
     j+=k; 
     k=1; 
     p=j-i; 

ist der schwierige Teil. Wir haben eine Nichtübereinstimmung gefunden, die lexikographisch später ist als unsere Referenz-Zeichenkette, also springen wir zum Ende des bisher übereinstimmenden Textes und beginnen von dort aus zu matchen. Wir erhöhen auch p (unseren Schritt). Warum können wir alle Startpunkte zwischen j und j + k überspringen? Dies liegt daran, dass die mit i beginnende Zeichenfolge lexikografisch am kleinsten ist, und wenn das Ende der aktuellen j-Zeichenfolge größer ist als die Zeichenfolge bei i, dann ist jedes Suffix der Zeichenfolge bei j größer als die Zeichenfolge bei i.

Schließlich

} else if (a==b && k!=p) { 
     k++; 
    } else { 
     j+=p; 
     k=1; 

diese prüft nur, dass die Zeichenfolge der Länge p bei i-Wiederholungen beginnen.

** weiter bearbeiten * Wir tun dies, k bis k == p durch Erhöhen, Prüfen, dass das k-ten Zeichen des Strings ab i die k-te Zeichen der Zeichenkette entspricht bei j beginnen. Sobald k p erreicht, beginnen wir erneut mit dem Scannen des nächsten angenommenen Auftretens der Zeichenkette.

Noch weiter bearbeiten zu versuchen, Jethros Fragen zu beantworten.

Zuerst: die k != p in else if (a==b && k!=p) Hier haben wir eine Übereinstimmung, in der die k'th und alle vorherigen Zeichen in den Strings beginnend bei i und j gleich sind. Die Variable p repräsentiert die Länge, die wir für die sich wiederholende Zeichenfolge halten. Wenn , eigentlich k < p, so stellen wir sicher, dass die p-Zeichen an der Zeichenkette, die bei i beginnt, die gleichen sind wie die p-Zeichen der Zeichenkette, die bei j beginnt. Wenn k == p (das letzte else) wir sollten an einem Punkt sein, wo die Zeichenfolge beginnend mit j + k gleich aussieht wie die Zeichenfolge beginnend bei j, so erhöhen wir j um p und setzen k zurück auf 1 und zurück zum Vergleich der beiden Zeichenfolgen.

Zweitens: Ja, ich glaube, Sie haben Recht, es sollte ich zurückkehren. Ich war Missverständnis, die Bedeutung von „Minimum zyklische Verschiebung“

Answer 2

es das gleiche wie dieser Algorithmus sein kann, Erklärung dessen kann here finden:

int ComputeMaxSufPos(string w) 
{ 
    int i = 0, n = w.Length; 
    for (int j = 1; j < n; ++j) 
    { 
     int c, k = 0; 
     while ((c = w[(i + k) % n].CompareTo(w[(j + k) % n])) == 0 && k != n) 
     { k++; } 
     j += c > 0 ? k/(j - i) * (j - i) : k; 
     i = c > 0 ? j : i; 
    } 
    return i; 
}