Wie die Periode einer Zeichenfolge finden

Question

ich vom Benutzer eine Eingabe nehmen und seine Zeichenkette mit einem bestimmten Teilkette, die sich alle durch den Strang wiederholt. Ich muss den Teilstring oder seine Länge AKA-Periode ausgeben.

Say

S1 = AAAA // substring is A 
S2 = ABAB // Substring is AB 
S3 = ABCAB // Substring is ABC 
S4 = EFIEFI // Substring is EFI 

ich mit einem einzelnen Zeichen beginnen könnte und prüfen, ob es als nächstes Zeichen gleich ist, wenn dies nicht der Fall, ich habe es mit zwei Zeichen mit drei dann tun konnte, und so weiter. Dies wäre ein O (N^2) -Algo. Ich habe mich gefragt, ob es eine elegantere Lösung dafür gibt.

Answer 1

Sie können dies in linearer Zeit und konstantem zusätzlichen Raum tun, indem Sie die Periode jedes Präfixes der Zeichenfolge induktiv berechnen. Ich kann mich nicht an die Details erinnern (es gibt mehrere Dinge, die richtig zu machen sind), aber Sie finden sie in Abschnitt 13.6 von "Textalgorithmen" von Crochemore und Rytter. (Und Sie können eine pdf-Kopie dieses Buches auf der Website von Maxime Crochemore kostenlos finden!)

Answer 2

Nun, wenn jedes Zeichen in der Eingabezeichenfolge Teil der sich wiederholenden Teilkette ist, dann alles, was Sie tun müssen, ist erste Zeichen zu speichern und vergleichen es mit dem Rest der eins nach dem anderen Zeichen der Zeichenfolge. Wenn Sie eine Übereinstimmung finden, ist die Zeichenfolge, bis die übereinstimmende eine wiederkehrende Zeichenfolge ist.

Answer 3

Sie können einen Suffixbaum für die gesamte Zeichenfolge in linearer Zeit erstellen (der Suffixbaum kann einfach online nachgeschlagen werden) und dann rekursiv die Anzahl der Suffixbaumblätter (Vorkommen des Suffixpräfixes) N (v) unter jedem internen Knoten v des Suffixbaums. Berechnen und speichern Sie rekursiv die Länge jedes Suffixpräfixes L (v) an jedem Knoten des Baums. Dann wurde in einem internen Knoten v in dem Baum, der Suffix-Präfix bei V codiert ist eine Wiederholungssequenz, die die Zeichenfolge erzeugt, wenn N (v) die Gesamtlänge der Zeichenkette entspricht durch L dividiert (v).

Answer 4

Lassen Sie mich annehmen, dass die Länge der Zeichenfolge n mindestens doppelt so groß ist wie die Periode p.

Algorithmus

1. Lassen m = 1 und S die gesamte Zeichenkette
2. Nehmen m = m * 2
   • das nächste Vorkommen der Teil S finden [: m]
   • Let k der Beginn des nächsten Auftreten sein
   • überprüfen Sie, ob S [: k] ist die Zeit
   • wenn nicht gehen zu 2.

Beispiel

Angenommen, wir haben einen String

CDCDFBFCDCDFDFCDCDFBFCDCDFDFCDC 

Für jede Leistung m von 2 finden wir Wiederholungen der ersten 2^m Zeichen. Dann erweitern wir diese Sequenz auf ihr zweites Auftreten. Beginnen wir mit 2^1 so CD.

CDCDFBFCDCDFDFCDCDFBFCDCDFDFCDC 
CDCD CDCD CDCD CDCD CD 

Wir erstrecken sich nicht CD da das nächste Auftreten gerade danach ist. Allerdings ist CD nicht der Teil wir das so läßt die nächste Leistung suchen: 2^2 = 4 und Teilzeichenfolge CDCD.

CDCDFBFCDCDFDFCDCDFBFCDCDFDFCDC 
CDCD CDCD 

Jetzt erweitern wir unsere Zeichenfolge auf die erste Wiederholung.Wir bekommen

CDCDFBF 

wir überprüfen, ob dies periodisch ist. Es ist nicht so, wir gehen weiter. Wir versuchen, 2^3 = 8, so CDCDFBFC

CDCDFBFCDCDFDFCDCDFBFCDCDFDFCDC 
CDCDFBFC  CDCDFBFC  

wir versuchen, zu erweitern und wir bekommen

CDCDFBFCDCDFDF 

und dies in der Tat ist unsere Zeit.

Ich erwarte, dass dies in O (n log n) mit einem KMP-ähnlichen Algorithmus funktioniert, um zu überprüfen, wo eine gegebene Zeichenkette erscheint. Beachten Sie, dass einige Randfälle hier noch ausgearbeitet werden sollten.

Intuitiv sollte dies funktionieren, aber meine Intuition scheiterte schon einmal an diesem Problem, also bitte korrigiert mich, wenn ich falsch liege. Ich werde versuchen, einen Beweis zu finden.

Ein sehr nettes Problem obwohl.