Ein gedrehtes Palindrom ist wie "1234321", "3432112". Die naive Methode wird die Saite in verschiedene Stücke zerlegen und sie zurückkonstruieren und sehen, ob die Saite ein Palindrom ist. Das würde O (n ^ 2) benötigen, da es n Schnitte gibt und für jeden Schnitt brauchen wir O (n), um zu prüfen, ob die Kette ein Palindrom ist. Ich frage mich, ob es eine bessere Lösung als diese gibt. Ich schätze, bitte, bitte.
Danke!
Laut diesem Wikipedia-Artikel ist es möglich, dass jeder String S der Länge n in der Zeit O (n) ein Array A der gleichen Größe berechnet, so dass:
A [i] == 1 wenn das Präfix von S der Länge i ein Palindrom ist.
Der Algorithmus sollte in:
gefunden werden könnenManacher, Glenn (1975), "Ein neuer linearer" Online "-Algorithmus für Finden des kleinsten anfänglichen Palindroms einer Zeichenkette "
Mit anderen Worten können wir überprüfen, welche Präfixe der Zeichenkette in linearer Zeit Palindrome sind. Wir werden dieses Ergebnis verwenden, um das vorgeschlagene Problem zu lösen.
Jedes (nicht rotierende) Palindrom S hat die folgende Form S = psxs ^ Rp ^ R.
wobei "x" das Zentrum des Palindroms ist (entweder leere Zeichenfolge oder eine Zeichenfolge), "p" und "s" sind (möglicherweise leere) Zeichenketten und "s ^ R" bedeutet "s" Zeichenkette umgekehrt.
Jedes rotierende Palindrom, das aus dieser Zeichenkette erzeugt wird, hat eine der beiden folgenden Formen (für einige p):
Das ist richtig, weil Sie wählen können, ob Sie einen Teilstring vor oder nach der Mitte des Palindroms schneiden und dann am anderen Ende einfügen möchten.
Wie man sehen kann, sind die Teilstrings "p ^ Rp" und "sxs ^ R" beide Palindrome, eine von der geraden Länge und die andere von ungerader Länge, wenn S von ungerader Länge ist.
Wir können den im Wikipedia-Link erwähnten Algorithmus verwenden, um zwei Arrays A und B zu erstellen. Das Array A wird erstellt, indem geprüft wird, welche Präfixe Palindrome und B für Suffixe sind. Dann suchen wir nach einem Wert i, so dass A [i] == B [i] == 1, so dass entweder Präfix oder Suffix gerade Länge hat. Wir werden einen solchen Index finden, wenn die vorgeschlagene Zeichenkette ein gedrehtes Palindrom ist und der gerade Teil die "p ^ Rp" Teilzeichenkette ist, so dass wir das ursprüngliche Palindrom leicht wiederherstellen können, indem wir die Hälfte dieser Zeichenkette zum anderen Ende der Zeichenkette bewegen. p>
Eine Bemerkung zur Lösung von rks, diese Lösung funktioniert nicht, da für eine Saite S = 1121 die Saite 11211121 erzeugt wird, deren Palindromlänge länger oder gleich der Länge von S ist, aber sie ist nicht rotiert Palindrom. Wenn wir die Lösung so ändern, dass sie prüft, ob es ein Palindrom der Länge der Länge von S gibt, würde es funktionieren, aber ich sehe keine direkte Lösung, wie man den Algorithmus nach der längsten Teilkette so verändern kann, dass sie es ist würde nach Teilstring fester Länge (len (S)) suchen. (Ich habe dies nicht als Kommentar unter der Lösung geschrieben, da ich neu bei Stackoverflow bin und nicht genug Reputation dafür habe)
Zweite Bemerkung - Es tut mir leid, den Algorithmus von Manacher nicht einzubeziehen, wenn jemand einen Link zu der Idee des Algorithmus oder einer Implementierung hat, bitte fügen Sie ihn in die Kommentare ein.
Verketten Sie die Saite mit sich selbst und machen Sie dann die klassische Palindrom-Suche in der neuen Saite. Wenn Sie ein Palindrom finden, dessen Länge länger oder gleich der Länge Ihrer ursprünglichen Saite ist, wissen Sie, dass Ihre Saite ein gedrehtes Palindrom ist.
Für Ihr Beispiel würden Sie Ihre Suche in 34321123432112 durchführen und 21123432112 finden, was länger ist als Ihre ursprüngliche Zeichenfolge, also ist es ein gedrehtes Palindrom.
BEARBEITEN: Wie Richard Stefanec bemerkte, schlägt mein Algorithmus auf 1121 fehl, und er schlug vor, dass wir den >= Test auf die Länge um = ändern.
EDIT2: Es sollte beachtet werden, dass das Finden eines Palindroms einer gegebenen Größe nicht offensichtlich einfach ist. Lesen Sie die Diskussion unter Richard Stefanec Beitrag für weitere Informationen.
Ich möchte eine einfache Lösung vorschlagen, die nur konventionelle Algorithmen verwendet. Es wird kein schwierigeres Problem lösen, aber es sollte für Ihre Aufgabe ausreichen. Es ist ein wenig ähnlich zu den anderen beiden vorgeschlagenen Lösungen, aber keiner von ihnen scheint zu kurz zu sein, um sorgfältig zu lesen.
Erster Schritt: Verkettung der Zeichenfolge mit sich selbst ( abvc - & gt; abvcabvc ) wie in allen anderen vorgeschlagenen Lösungen.
Zweiter Schritt: Rabin-Karp Vorberechnung (welche verwendet rolling Hash) für die neu erhaltene Zeichenfolge und umgekehrt.
Dritter Schritt: Die Zeichenfolge muss die Länge n haben. Überprüfen Sie für jeden Index i in 0...n-1 , ob der Teilstring der verdoppelten Zeichenkette [i, i + n - 1] in konstanter Zeit palindrome ist, indem Sie die Rabin-Karp-Vorberechnungen verwenden (im Grunde sollte der erhaltene Wert für die Teilkette in Vorwärts- und Rückwärtsrichtung) gleich sein).
Fazit: wenn im dritten Schritt ein Palindrom gefunden wurde - dann wird die Saite palindrom gedreht. Wenn nicht - dann ist es nicht.
PS: Rabin Karp benutzt Hashes und Kollisionen sind sogar für nicht übereinstimmende Strings möglich. Daher ist es eine gute Idee, die Brute-Force-Prüfung auf Gleichheit zu überprüfen, wenn dies durch die Hash-Prüfungen ausgelöst wird. Wenn die Hash-Funktionen in Rabin Karp jedoch gut sind, sollte die amortisierte Geschwindigkeit der Lösung O(n) bleiben.
Sie können das gleiche Muster am Ende des ursprünglichen Musters hinzufügen. Zum Beispiel ist das Muster 1234321, dann können Sie das gleiche Muster zum Ende 12343211234321 hinzufügen. Nachdem Sie dies getan haben, können Sie die KMP- oder andere Teilstring-Entsprechung algotithms verwenden, um die gewünschte Zeichenfolge zu finden. Wenn Übereinstimmung, kehrt die Eingabe zurück.
Tags und Links algorithm palindrome