Gibt es einen Algorithmus zum Überprüfen, ob eine Zeichenfolge eine Verkettung von Palindromen ist?

Gibt es einen linearen Zeitalgorithmus, um zu überprüfen, ob eine Folge von Zeichen eine Verkettung von Palindromen ist? Das einzige, was mir in den Sinn kommt, ist die naive Lösung:

1. k = 1
2. Split string into k substrings (all possibilities) and check
3. k++
4. repeat

Hinweis: Die Antwort lautet trivial Ja, wenn Längen-1-Strings als Palindrome definiert sind. Nehmen wir an, dass dies nicht der Fall ist.

algorithms efficiency strings saadtaame
quelle

Wenn Sie triviale Palindrome der Länge 1 zulassen (z. B. ist die Zeichenfolge "a" ein Palindrom), sind alle Zeichenfolgen Verkettungen von Palindromen.

Matt Lewis

Ist es nützlich oder eine Übung?

Jan Hudec

@MattLewis Sie können versuchen, die Anzahl der Palindrome zu minimieren. Jan, warum? Klingt nach einer schönen Übung in dynamischer Programmierung.

Pål GD

@Haile Nein. Nur disjunkte Palindrome.

Saadtaame

Norvig hat umfangreiche Arbeiten an Palindromen durchgeführt. Sie könnten an dieser Seite interessiert sein: norvig.com/palindrome.html

robowolverine

Antworten:

Angenommen, Sie möchten disjunkte Palindrome, ist dies als PALSTAR-Problem bekannt, und es gibt einen linearen Zeitalgorithmus von Zvi Galil und Joel Seiferas. Ein linearer Online-Erkennungsalgorithmus für "Palstar" .

Eine Erklärung des Algorithmus finden Sie im Buch hier: Textalgorithmen (siehe verlinkte Seite und die vorhergehenden Seiten).

Wenn Sie mit einem quadratischen Zeitalgorithmus einverstanden sind, scheint die einfache dynamische Programmierung zu funktionieren.

Wenn ein String , behalten wir ein Array bei, das uns sagt, ob in Palindrome zerlegt werden kann. $s[1,\dots n]$ $s[1,\dots j]$

Wir pflegen auch eine 2D-Tabelle, die uns sagt, ob ein Palindrom ist oder nicht. Dies können wir in -Zeit konstruieren, indem wir ein Zentrum auswählen und zwei Zeiger nach außen bewegen, um nach Palindromen mit diesem Zentrum zu suchen. Tun Sie dies für jedes mögliche Zentrum: Zentren, wobei jedes Zeit benötigt. $s[i, \dots j]$ $O(n^2)$ $\Theta(n)$ $O(n)$

Jetzt können Sie überprüfen, ob in Palindrome zerlegt werden kann, indem Sie für jede prüfen, ob zerlegt werden kann und ob ist ein Palindrom (unter Verwendung der obigen 2D-Tabelle). Dies ergibt einen Zeit- und Raumalgorithmus. $s[1, \dots j+1]$ $1 \le i \le j-1$ $s[1,\dots i]$ $s[i+1,\dots, j+1]$ $\Theta(n^2)$ $\Theta(n^2)$

Die Raumnutzung kann auf reduziert werden, wenn Sie den Online-Algorithmus von Manacher verwenden, um zu berechnen, ob ein Palindrom ist (wenn von nach gehe ). , im Grunde die 2D-Tabelle loswerden. $O(n)$ $s[i+1,\dots j+1]$ $i$ $j-1$ $1$

Aryabhata
quelle

Dies ist ähnlich wie mein Algorithmus, ich habe nur den Vorverarbeitungsteil nicht erklärt, um ihn als Übung dem OP zu überlassen, aber ich weiß nicht, warum sich niemand um meinen Algorithmus kümmerte :)

@SaeedAmiri: Hast du den ersten Teil meiner Antwort gelesen, in dem die lineare Zeit erwähnt wird? Wie ist es ähnlich? Übrigens hat OP die Frage geändert, um nach einem linearen Zeitalgorithmus zu fragen, der Ihre Antwort und die zweite Hälfte meiner Antwort irrelevant macht. Ich habe diesen Teil nicht aus meiner Antwort gelöscht, weil ich den Manacher-Algorithmus erwähnen wollte, der bewirkt, dass der dynamische Programmieralgorithmus nur O (n) -Raum verwendet (und den Vorverarbeitungsschritt beseitigt), und er könnte für andere Leute, die dies tun, immer noch relevant sein zufällig auf diese Frage stoßen

Aryabhata

Nehmen Sie es nicht in Serie, es ist nur ein Scherz, ich mag Ihre Antworten im Allgemeinen, ich denke, es gibt ein Problem mit meinem englischen Schreiben, weil OP meine Lösung nicht verstanden hat und es nicht in meiner Stimmung war, sie per Bild zu zeichnen . Aber guter Punkt OP hat kürzlich seine Frage geändert, und möglicherweise gibt es eine Lösung, die dem Manacher-Algorithmus ähnelt (aber wirklich nicht einfach ist).

@ SaeedAmiri: Ich verstehe, keine Sorge dann :-)

Aryabhata

Wenn eine Überlappung zulässig ist, kann dies in linearer Zeit (in der Größe der Eingabezeichenfolge) erfolgen.

Einige Definitionen

Definieren wir das Konzept des maximalen Palindroms :

Ein maximales Palindrom mit dem Radius k eines Strings S ist ein Teilstring S ', so dass

Ausgehend von der Mitte liest S 'die gleichen k Zeichen in beide Richtungen
aber nicht für k + 1 Zeichen
k> 1 (ein einzelnes Zeichen ist also kein Palindrom)

Wenn beispielsweise S = banana, dann S' = ananaist ein maximales Palindrom mit Radius 2.

Ein maximales Palindrom ist ein maximales Palindrom mit dem Radius k für einige k.

Wenn zum Beispiel S = banana, "ana", "anana", sind alle seine maximalen Palindrome.

Mit maximalen Palindromen

Wenn wir nun alle maximalen Palindrome einer Zeichenfolge lokalisieren könnten , wäre es einfach zu überprüfen, ob die gesamte Zeichenfolge eine Verkettung von Palindromen ist.

Nimm S = abbaccazayaz. Seine maximalen Palindrome sind:

abba, zentriert zwischen Position 2 und 3, Radius = 2
acca, zentriert zwischen Position 5 und 6, Radius = 2
Zayaz, zentriert in Position 10, Radius = 2

"abba" überspannt also [1..4], "acca" über [4..7], "zayaz" über [8..12]. Da sich die Verkettung dieser drei Palindrome (Überlappung ist zulässig?) Über die gesamte Zeichenfolge erstreckt, folgt, dass "abbaccazayaz" die Verkettung von Palindromen ist.

Berechnung maximaler Palindrome in linearer Zeit

Nun stellt sich heraus, dass wir alle maximalen Palindrome einer Zeichenkette S in linearer Zeit lokalisieren können !*

Die Idee ist, einen Suffixbaum für S zu verwenden, der mit den niedrigsten gemeinsamen Vorfahrenabfragen mit konstanter Zeit ausgestattet ist .

Wir können also überprüfen, ob eine Zeichenfolge S der Länge m eine Verkettung von Palindromen in O (n) -Zeit ist.

* Gusfield, Dan (1997), "9.2 Finden aller maximalen Palindrome in linearer Zeit", Algorithmen für Strings, Bäume und Sequenzen

Haile
quelle

k

$k$ nanaanana

Das "Anana" -Ding bearbeitet, danke. Außerdem fordert OP keine minimale Palindromsequenz an: Da ein einzelnes Zeichen kein Palindrom ist, müssen wir nur entscheiden, ob die Eingabezeichenfolge eine Verkettung von Palindromen ist oder nicht.

Haile

k = 1

$k=1$

@Khaur Es dauert nur loglineare Zeit, wenn die Intervalle nicht sortiert sind. In diesem Fall sind sie wahrscheinlich.

Yuval Filmus

In den Kommentaren zur Frage fügt das OP ausdrücklich hinzu, dass überlappende Palindrome nicht zulässig sind. Diese Lösung in der gegenwärtigen Form ist also nicht das, wonach das OP sucht. Ich denke, dass diese Lösung modifiziert werden kann, um auch den nicht überlappenden Fall zu lösen, mit einigen Überlegungen und höchstens quadratischer Komplexität. Aber ich habe nicht viel darüber nachgedacht.

Paresh

Angenommen, Palindrom [] [] ist ein Array und Palindrom (i, j) ist eine Funktion, die prüft, ob der Teilstring von i nach j Palindrom ist und 1 zurückgibt, wenn es Palindrom ist, oder unendlich zurückgibt, wenn es kein Palindrom ist, und Sie nach der kleinsten Zahl suchen Erstellen Sie von unten nach oben Partitionen:

P. ein l ich n d r Ö m e [ich]] [ich]] = 1.

$Palindrome[i][i] = 1.$

\forall 0 \leq ich < j < n :: P. ein l ich n d r Ö m e [ich]] [j]] = Mindest {P. ein l ich n d r Ö m e (ich, j), \underset{ich \leq k < j}{Mindest} {P. ein l ich n d r Ö m e [ich, k]] + P. ein l ich n d r Ö m e [ich + 1, k]]}}}}

$\forall 0\le i < j < n : Palindrome[i][j] = \min\{Palindrome(i,j), \min_{i\le k<j} \{Palindrome[i,k] + Palindrome[i+1,k]\}\}$

$O(n^2)$ $O(n)$ $O(n^3)$ $O(n^2)$

quelle

Können Sie anhand eines Beispiels veranschaulichen? Sprich:abbaaccaabba.

Saadtaame

@saadtaame, OK, hier ist es nicht möglich, eine Tabelle zu erstellen (in cs.stackexchange), oder ich konnte keinen Weg finden, dies zu tun. Ich werde dies irgendwo tun und das Bild später hier einfügen. Aber jetzt versuchen Sie es selbst zu verstehen, beginnen mit Teilzeichenfolgen der Länge 1 und überprüfen dann Palindrome der Länge 2, ... und so weiter.