dynamic-programming
Teilsequenzbezogene Algorithmen
Suche…
Längste häufige Folge
Eine der wichtigsten Implementierungen der dynamischen Programmierung besteht darin, die längste häufige Teilsequenz herauszufinden. Lassen Sie uns zuerst einige der grundlegenden Terminologien definieren.
Folge:
Eine Untersequenz ist eine Sequenz, die aus einer anderen Sequenz abgeleitet werden kann, indem einige Elemente gelöscht werden, ohne die Reihenfolge der übrigen Elemente zu ändern. Nehmen wir an, wir haben einen String ABC . Wenn wir null oder ein oder mehr als ein Zeichen aus dieser Zeichenfolge löschen, erhalten wir die Untersequenz dieser Zeichenfolge. Die Untersequenzen der Zeichenfolge ABC sind also { "A" , "B" , "C" , "AB" , "AC" , "BC" , "ABC" , "" }. Auch wenn wir alle Zeichen entfernen, ist die leere Zeichenfolge auch eine Folge. Um die Untersequenz herauszufinden, haben wir für jedes Zeichen in einer Zeichenfolge zwei Optionen - entweder nehmen wir das Zeichen oder nicht. Wenn also die Länge der Zeichenfolge n ist , gibt es 2 n Untersequenzen dieser Zeichenfolge.
Längste häufige Folge:
Wie der Name vermuten lässt, ist die längste gemeinsame Untersequenz (LCS) von allen gemeinsamen Untersequenzen zwischen zwei Strings diejenige mit der maximalen Länge. Zum Beispiel: Die gemeinsamen Untersequenzen zwischen "HELLOM" und "HMLD" sind "H" , "HL" , "HM" usw. Hier ist "HLL" die längste gemeinsame Untersequenz, die die Länge 3 hat.
Brute-Force-Methode:
Wir können alle Untersequenzen von zwei Strings durch Rückverfolgung erzeugen. Dann können wir sie vergleichen, um die üblichen Untersequenzen herauszufinden. Danach müssen wir die maximale Länge herausfinden. Wir haben bereits gesehen, dass es 2 n Untersequenzen einer Folge der Länge n gibt . Es würde Jahre dauern, das Problem zu lösen, wenn unser n 20-25 kreuzt.
Dynamische Programmiermethode:
Gehen wir mit einem Beispiel an unsere Methode heran. Angenommen, wir haben zwei Zeichenketten abcdaf und acbcf . Bezeichnen wir diese mit s1 und s2 . Die längste gemeinsame Untersequenz dieser beiden Zeichenfolgen ist also "abcf" mit der Länge 4. Ich erinnere Sie daran, dass Teilfolgen in der Zeichenfolge nicht fortlaufend sein müssen. Um "abcf" zu konstruieren, haben wir "da" in s1 und "c" in s2 ignoriert. Wie finden wir das mit der dynamischen Programmierung heraus?
Wir beginnen mit einer Tabelle (einem 2D-Array), die alle Zeichen von s1 in einer Reihe und alle Zeichen von s2 in der Spalte enthält. Hier ist die Tabelle 0-indexiert und wir setzen die Zeichen von 1 bis weiter. Wir werden die Tabelle für jede Zeile von links nach rechts durchqueren. Unser Tisch wird wie folgt aussehen:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Jede Zeile und Spalte repräsentiert dabei die Länge der längsten gemeinsamen Untersequenz zwischen zwei Zeichenfolgen, wenn wir die Zeichen dieser Zeile und Spalte nehmen und zum Präfix hinzufügen. Zum Beispiel: Tabelle [2] [3] repräsentiert die Länge der längsten gemeinsamen Untersequenz zwischen "ac" und "abc" .
Die 0-te Spalte repräsentiert die leere Teilsequenz von s1 . In ähnlicher Weise repräsentiert die 0-te Zeile die leere Teilsequenz von s2 . Wenn wir eine leere Untersequenz einer Zeichenfolge nehmen und versuchen, sie mit einer anderen Zeichenfolge abzugleichen, egal wie lang die zweite Teilzeichenfolge ist, wird die gemeinsame Untersequenz die Länge 0 haben. So können wir die 0-ten Zeilen und die 0-ten Spalten mit 0 füllen. Wir bekommen:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Lass uns anfangen. Wenn wir Tabelle [1] [1] füllen, fragen wir uns, ob wir eine Zeichenfolge a und eine andere Zeichenfolge a und nichts anderes hatten. Was ist die längste gemeinsame Folge hier? Die Länge des LCS wird hier 1 betragen. Nun wollen wir uns Tabelle [1] [2] ansehen. Wir haben string ab und string a . Die Länge des LCS ist 1. Wie Sie sehen, sind die restlichen Werte auch 1 für die erste Zeile, da sie nur die Zeichenfolge a mit abcd , abcda , abcdaf berücksichtigt . So wird unser Tisch aussehen:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Für Reihe 2, die jetzt c enthält . Für Tabelle [2] [1] haben wir ac auf der einen und a auf der anderen Seite. Die Länge des LCS ist also 1. Woher haben wir diese 1? Von oben bezeichnet der LCS einen zwischen zwei Teilstrings. Wir sagen also, wenn s1 [2] und s2 [1] nicht gleich sind, dann ist die Länge der LCS das Maximum der Länge der LCS oben oder links . Die Länge des LCS an der Spitze bedeutet, dass wir das aktuelle Zeichen nicht aus s2 nehmen . Wenn Sie die Länge des LCS auf der linken Seite angeben, bedeutet dies ebenfalls, dass wir nicht das aktuelle Zeichen von s1 nehmen , um das LCS zu erstellen. Wir bekommen:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Unsere erste Formel lautet also:
if s2[i] is not equal to s1[j]
Table[i][j] = max(Table[i-1][j], Table[i][j-1]
endif
Weiter für Tabelle [2] [2] haben wir string ab und ac . Da c und b nicht gleich sind, setzen wir hier das Maximum von oben oder links. In diesem Fall ist es wieder 1. Danach haben wir für Tabelle [2] [3] die Zeichenfolgen abc und ac . Diese aktuellen Werte für Zeile und Spalte sind gleich. Nun ist die Länge des LCS gleich der maximalen Länge von LCS + 1. Wie erhalten wir die maximale Länge von LCS? Wir prüfen den Diagonalwert, der die beste Übereinstimmung zwischen ab und a darstellt . Aus diesem Zustand haben wir für die aktuellen Werte ein weiteres Zeichen zu s1 und s2 hinzugefügt, das zufällig dasselbe war. Die Länge von LCS wird sich natürlich verlängern. Wir setzen 1 + 1 = 2 in Tabelle [2] [3] . Wir bekommen,
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | 1 | 2 | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Unsere zweite Formel lautet also:
if s2[i] equals to s1[j]
Table[i][j] = Table[i-1][j-1] + 1
endif
Wir haben beide Fälle definiert. Mit diesen beiden Formeln können wir die gesamte Tabelle füllen. Nach dem Auffüllen der Tabelle sieht das so aus:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | 1 | 2 | 2 | 2 | 2 |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | 1 | 2 | 2 | 2 | 2 | 2 |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | 1 | 2 | 3 | 3 | 3 | 3 |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | 1 | 2 | 3 | 3 | 3 | 4 |
+-----+-----+-----+-----+-----+-----+-----+-----+
Die Länge des LCS zwischen s1 und s2 beträgt Tabelle [5] [6] = 4 . Hier sind 5 und 6 die Länge von s2 bzw. s1 . Unser Pseudo-Code lautet:
Procedure LCSlength(s1, s2):
Table[0][0] = 0
for i from 1 to s1.length
Table[0][i] = 0
endfor
for i from 1 to s2.length
Table[i][0] = 0
endfor
for i from 1 to s2.length
for j from 1 to s1.length
if s2[i] equals to s1[j]
Table[i][j] = Table[i-1][j-1] + 1
else
Table[i][j] = max(Table[i-1][j], Table[i][j-1])
endif
endfor
endfor
Return Table[s2.length][s1.length]
Die zeitliche Komplexität für diesen Algorithmus ist: O (mn) wobei m und n die Länge der einzelnen Strings bedeuten.
Wie finden wir die längste gemeinsame Folge heraus? Wir beginnen von rechts unten. Wir werden prüfen, woher der Wert kommt. Wenn der Wert von der Diagonale kommt, das heißt, wenn Tabelle [i-1] [j-1] gleich Tabelle [i] [j] -1 ist , drücken wir entweder s2 [i] oder s1 [j] (beide sind gleich) und bewegen sich diagonal. Wenn der Wert von oben kommt, heißt das, wenn Tabelle [i-1] [j] gleich Tabelle [i] [j] ist , bewegen wir uns nach oben. Wenn der Wert von links kommt, heißt das, wenn Tabelle [i] [j-1] gleich Tabelle [i] [j] ist , bewegen wir uns nach links. Wenn wir die linke oder oberste Spalte erreichen, ist unsere Suche beendet. Dann ziehen wir die Werte aus dem Stapel und drucken sie. Der Pseudo-Code:
Procedure PrintLCS(LCSlength, s1, s2)
temp := LCSlength
S = stack()
i := s2.length
j := s1.length
while i is not equal to 0 and j is not equal to 0
if Table[i-1][j-1] == Table[i][j] - 1 and s1[j]==s2[i]
S.push(s1[j]) //or S.push(s2[i])
i := i - 1
j := j - 1
else if Table[i-1][j] == Table[i][j]
i := i-1
else
j := j-1
endif
endwhile
while S is not empty
print(S.pop)
endwhile
Zu beachten ist: wenn sowohl Tabelle [i-1] [j] als auch Tabelle [i] [j-1] gleich Tabelle [i] [j] und Tabelle [i-1] [j-1] ist gleich zu Tabelle [i] [j] -1 kann es für diesen Moment zwei LCS geben. Dieser Pseudo-Code berücksichtigt diese Situation nicht. Sie müssen dies rekursiv lösen, um mehrere LCSs zu finden.
Die zeitliche Komplexität für diesen Algorithmus ist: O (max (m, n)) .
Längste zunehmende Folge
Die Aufgabe besteht darin, die Länge der längsten Teilfolge in einem gegebenen Array von Ganzzahlen zu ermitteln, so dass alle Elemente der Teilfolge aufsteigend sortiert werden. Beispielsweise ist die Länge der am längsten zunehmenden Teilsequenz (LIS) für {15, 27, 14, 38, 26, 55, 46, 65, 85} 6 und die am längsten zunehmende Teilsequenz ist {15, 27, 38, 55. 65, 85} . Für {3, 4, -1, 0, 6, 2, 3} ist die Länge von LIS 4 und die Untersequenz ist {-1, 0, 2, 3} . Wir werden dynamische Programmierung verwenden, um dieses Problem zu lösen.
Nehmen wir das zweite Beispiel: Item = {3, 4, -1, 0, 6, 2, 3} . Wir beginnen mit einem Array dp der gleichen Größe unserer Sequenz. dp [i] steht für die Länge des LIS, wenn wir den i- ten Punkt unserer ursprünglichen Sequenz enthalten. Ganz am Anfang wissen wir, dass für jeden einzelnen Artikel mindestens die am längsten wachsende Teilsequenz die Länge 1 hat . Das heißt, wenn man das einzelne Element selbst betrachtet. Also initialisieren wir das dp- Array mit 1 . Wir haben zwei Variablen i und j . Zunächst wird i 1 und j 0 sein wird. Unser Array wird wie folgt aussehen:
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
Die Zahl über dem Array repräsentiert das entsprechende Element unserer Sequenz. Unsere Strategie wird sein:
if Item[i] > Item[j]
dp[i] := dp[j] + 1
Das heißt , wenn das Element bei i größer als Element an j ist, die Länge des LIS , das Element an j enthält, durch Länge zunehmen , wenn man 1 - Element bei i mit ihm gehört. In unserem Beispiel ist für i = 1 und j = 0 Item [i] größer als Item [j] . Also ist dp [i] = dp [j] + 1 . Unser Array wird wie folgt aussehen:
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
Bei jedem Schritt werden wir j bis zu i erhöhen und dann j auf 0 zurückgesetzt und erhöhen i. Im Moment hat j i erreicht, also erhöhen wir i auf 2 .
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
Für i = 2 , j = 0 ist Item [i] nicht größer als Item [j] , also machen wir nichts und erhöhen j .
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
Für i = 2 , j = 1 ist Item [i] nicht größer als Item [j] , so dass wir nichts tun, und da j seine Grenze erreicht hat, erhöhen wir i und setzen j auf 0 zurück .
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
Für i = 3 , j = 0 , ist Item [i] nicht größer als Item [j] , sodass wir nichts tun und j inkrementieren.
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
Für i = 3 , j = 1 , ist Item [i] nicht größer als Item [j] , so dass wir nichts tun und j inkrementieren.
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
Für i = 3 , j = 2 ist Item [i] größer als Item [j] , also ist dp [i] = dp [j] + 1 . Nachdem j seine Grenze erreicht hat, setzen wir j wieder auf 0 und erhöhen i .
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 2 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
Für i = 4 und j = 0 ist Item [i] größer als Item [j] , also ist dp [i] = dp [j] + 1 . Danach erhöhen wir j .
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 2 | 2 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
Für i = 4 und j = 1 ist Item [i] größer als Item [j] . Wir können auch feststellen, dass dp [i] = dp [j] + 1 uns 3 ergibt. Wenn wir also die LIS für Item [j] nehmen und Item [i] hinzufügen, erhalten wir eine bessere LIS { 3,4,6} als vorher {3,6}. Also setzen wir dp [i] = dp [j] + 1 . Dann erhöhen wir j .
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 2 | 3 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
Für i = 4 und j = 2 ist Item [i] größer als Item [j] . Wenn wir jedoch dp [i] = dp [j] + 1 setzen , erhalten wir 2 , was {-1,6} ist und nicht das beste {3,4,6}, das wir mit Item [ tun können. i] . Also werfen wir diesen weg. Wir fügen unserer Strategie eine Bedingung hinzu, das heißt:
if Item[i]>Item[j] and dp[i]<dp[j] + 1
dp[i] := dp[j] + 1
Wir erhöhen j um 1 . Nach dieser Strategie sieht es so aus, wenn wir unser dp- Array vervollständigen:
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 2 | 3 | 3 | 4 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
Jetzt durchlaufen wir dieses Array und ermitteln den maximalen Wert, der die Länge des LIS ist. Unser Pseudo-Code lautet:
Procedure LISLength(Item):
n := Item.length
dp[] := new Array(n)
for i from 0 to n
dp[i] := 1
end for
for i from 1 to n
for j from 0 to i
if Item[i]>Item[j] and dp[i]<dp[j] + 1
dp[i] := dp[j] + 1
end if
end for
end for
l := -1
for i from 0 to n
l := max(l, dp[i])
end for
Return l
Die zeitliche Komplexität dieses Algorithmus ist O(n²) wobei n die Länge der Sequenz ist.
Um die ursprüngliche Sequenz herauszufinden, müssen wir rückwärts iterieren und sie mit unserer Länge abgleichen. Das Verfahren ist:
Procedure LIS(Item, dp, maxLength):
i := Item.length
while dp[i] is not equal to maxLength
i := i - 1
end while
s = new Stack()
s.push(Item[i])
maxLength := maxLength - 1
current := Item[i]
while maxLength is not equal to 0
i := i-1
if dp[i] := maxLength and Item[i] < current
current := Item[i]
s.push(current)
maxLength := maxLength - 1
end if
end while
while s is not empty
x := s.pop
Print(s)
end while
Die zeitliche Komplexität dieses Algorithmus ist: O(n) .
Längste palindromische Folge
Was ist angesichts einer Zeichenfolge die längste palindromische Untersequenz (LPS) davon? Nehmen wir einen String agbdba . Das LPS dieser Saite ist abdba der Länge 5 . Denken Sie daran, da wir für Teilfolge suchen, die Charaktere müssen nicht in der ursprünglichen Zeichenfolge kontinuierlich sein. Der längste palindromische Teilstring der Sequenz wäre bdb der Länge 3 . Aber wir werden uns hier auf die Folge konzentrieren. Wir werden dynamische Programmierung verwenden, um dieses Problem zu lösen.
Zuerst nehmen wir ein 2D-Array mit der gleichen Größe unserer ursprünglichen Sequenz. Für unser Beispiel: S = "agbdba" nehmen wir das dp [6] [6] -Array. Hier stellt dp [i] [j] die Länge der LPS dar, die wir machen können, wenn wir die Zeichen von s [i] bis s [j] betrachten . Zum Beispiel. Wenn unsere Zeichenfolge aa wäre , würde dp [0] [1] 2 speichern. Jetzt betrachten wir unterschiedliche Längen unserer Saite und finden die längste mögliche Länge heraus, die wir daraus machen können.
Länge = 1 :
Hier betrachten wir jeweils nur 1 Zeichen. Wenn wir also eine Zeichenfolge der Länge 1 haben , welche LPS können wir haben? Die Antwort lautet natürlich 1 . Wie lagern? dp [i] [j] wobei i gleich j ist, repräsentiert eine Zeichenfolge der Länge 1 . Wir setzen also dp [0] [0] , dp [1] [1] , dp [2] [2] , dp [3] [3] , dp [4] [4] , dp [5] [ 5] bis 1 . Unser Array wird wie folgt aussehen:
+---+---+---+---+---+---+---+
| | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
| 0 | 1 | | | | | |
+---+---+---+---+---+---+---+
| 1 | | 1 | | | | |
+---+---+---+---+---+---+---+
| 2 | | | 1 | | | |
+---+---+---+---+---+---+---+
| 3 | | | | 1 | | |
+---+---+---+---+---+---+---+
| 4 | | | | | 1 | |
+---+---+---+---+---+---+---+
| 5 | | | | | | 1 |
+---+---+---+---+---+---+---+
Länge = 2 :
Diesmal betrachten wir Strings der Länge 2 . Wenn Sie nun Zeichenfolgen der Länge 2 betrachten , kann die maximale Länge von LPS 2 sein, und zwar nur dann, wenn die beiden Zeichen der Zeichenfolge identisch sind. Unsere Strategie wird also sein:
j := i + Length - 1
if s[i] is equal to s[j]
dp[i][j] := 2
else
dp[i][j] := 1
Wenn wir unser Array gemäß der Strategie für Länge = 2 füllen, erhalten wir:
+---+---+---+---+---+---+---+
| | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
| 0 | 1 | 1 | | | | |
+---+---+---+---+---+---+---+
| 1 | | 1 | 1 | | | |
+---+---+---+---+---+---+---+
| 2 | | | 1 | 1 | | |
+---+---+---+---+---+---+---+
| 3 | | | | 1 | 1 | |
+---+---+---+---+---+---+---+
| 4 | | | | | 1 | 1 |
+---+---+---+---+---+---+---+
| 5 | | | | | | 1 |
+---+---+---+---+---+---+---+
Länge = 3 :
Jetzt betrachten wir 3 Zeichen gleichzeitig für unsere ursprüngliche Zeichenfolge. Von nun an wird die LPS, die wir aus unserer Saite machen können, bestimmt durch:
- Wenn das erste und das letzte Zeichen übereinstimmen, haben wir mindestens zwei Elemente, aus denen wir das LPS + erstellen können, wenn wir das erste und das letzte Zeichen ausschließen.
- Wenn das erste und das letzte Zeichen nicht übereinstimmen, wird das LPS, das wir erstellen können, entweder aus dem ersten Zeichen oder dem letzten Zeichen, das wir bereits berechnet haben, ausgeschlossen.
Sommer zu machen,
j := i + Length - 1
if s[i] is equal to s[j]
dp[i][j] := 2 + dp[i+1][j-1]
else
dp[i][j] := max(dp[i+1][j], dp[i][j-1])
end if
Wenn wir das dp- Array für Length = 3 bis Length = 6 füllen, erhalten wir:
+---+---+---+---+---+---+---+
| | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
| 0 | 1 | 1 | 1 | 1 | 3 | 5 |
+---+---+---+---+---+---+---+
| 1 | | 1 | 1 | 1 | 3 | 3 |
+---+---+---+---+---+---+---+
| 2 | | | 1 | 1 | 3 | 3 |
+---+---+---+---+---+---+---+
| 3 | | | | 1 | 1 | 1 |
+---+---+---+---+---+---+---+
| 4 | | | | | 1 | 1 |
+---+---+---+---+---+---+---+
| 5 | | | | | | 1 |
+---+---+---+---+---+---+---+
Dies ist unser erforderliches dp- Array, und dp [0] [5] enthält die Länge des LPS. Unser Verfahren wird wie folgt aussehen:
Procedure LPSLength(S):
n := S.length
dp[n][n]
for i from 0 to n
dp[i][i] := 1
end for
for i from 0 to (n-2)
if S[i] := S[i+1]
dp[i][i+1] := 2
else
dp[i][i+1] := 1
end if
end for
Length := 3
while Length <= n
for i from 0 to (n - Length)
j := i + Length - 1
if S[i] is equal to s[j]
dp[i][j] := 2 + dp[i+1][j-1]
else
dp[i][j] := max(dp[i+1][j], dp[i][j-1])
end if
end for
Length := Length + 1
end while
Return dp[0][n-1]
Die zeitliche Komplexität dieses Algorithmus ist O(n²) , wobei n die Länge unserer angegebenen Zeichenfolge ist. Das Problem der längsten palindromischen Folge ist eng mit der längsten häufigen Folge verbunden. Wenn wir den zweiten String als Umkehrung des ersten Strings nehmen, die Länge berechnen und das Ergebnis drucken, ist dies die längste palindromische Untersequenz des angegebenen Strings. Die Komplexität dieses Algorithmus beträgt auch O(n²) .