Versuchen, das folgende Problem zu lösen:
Geben Sie für eine Zeichenfolge beliebiger Länge die längste Teilzeichenfolge an, die mehr als einmal in der Zeichenfolge ohne Überlappungen vorkommt.
Beispiel: Wenn die Eingabezeichenfolge ABCABCAB lautet, lautet die korrekte Ausgabe ABC . Sie könnten nicht ABCAB sagen, weil das nur zweimal auftritt, wenn die beiden Teilzeichenfolgen sich überlappen, was nicht erlaubt ist.
Gibt es eine Möglichkeit, dies für Strings mit ein paar tausend Zeichen schnell zu lösen?
(Und bevor jemand fragt, dies sind keine Hausaufgaben. Ich suche nach Möglichkeiten, das Rendern von Lindenmayer-Fraktalen zu optimieren, weil sie dazu neigen, mit einem naiven Turtle-Graphik-System übermäßig viel Zeit für das Zeichnen in hohen Iterationsstufen zu nehmen. )
Hier ist ein Beispiel für eine Zeichenfolge der Länge 11, die Sie verallgemeinern können
Setzen Sie die Chunk-Länge auf den Boden (11/2) = 5
Scannt die Zeichenkette in Blöcken von 5 Zeichen, die bis zur Suche nach Wiederholungen übrig sind. Es wird 3 Vergleiche geben
Hier ist ein (offensichtlich ungetesteter) Pseudocode:
%Vor%Es kann ein Fehler "von Eins nach Eins" sein, aber der Ansatz sollte vernünftig (und minimal) sein.
Es sieht aus wie ein Suffix-Baum-Problem. Erstellen Sie den Suffixbaum, und suchen Sie dann den größten komprimierten Zweig mit mehreren untergeordneten Elementen (tritt mehrmals in der ursprünglichen Zeichenfolge auf). Die Anzahl der Buchstaben in diesem komprimierten Zweig sollte der Größe der größten Teilsequenz entsprechen.
Ich habe etwas Ähnliches hier gefunden: Ссылка
Sieht so aus, als könnte es in O (n) gemacht werden.
Zuerst müssen wir das Startsymbol unserer Teilkette definieren und die Länge definieren. Iteriere alle möglichen Startpositionen und ermittle dann die Länge der binären Suche nach der Länge (wenn du substr mit der Länge a findest, kannst du mit der längeren Länge eine monotone Funktion finden, so dass die bin-Suche in Ordnung sein sollte). Dann finden Sie gleiche Teilstring ist N, mit KMP oder Rabin-Karp jeder lineare Algo ist in Ordnung. Gesamt N * N * log (N). Ist das zu viel Komplexität? Der Code ist etwas wie:
%Vor%Macht Sinn?
Tags und Links algorithm string language-agnostic