Longest Common Subsequence

Sei lcs(i, j) die Antwort für die Suffixe text1[i:] und text2[j:]. Betrachte ihre ersten Buchstaben. Sind sie gleich, ordne sie einander zu: Eine längste gemeinsame Teilfolge, die dieses Paar nicht verwendet, kann ihr erstes Paar durch dieses ersetzen, ohne kürzer zu werden. Die Antwort lautet also 1 + lcs(i+1, j+1).

Unterscheiden sich die Buchstaben, können sie nicht beide verwendet werden, da jeder nur mit einem späteren Buchstaben der jeweils anderen Zeichenkette abgeglichen werden könnte und sich die Paare dann kreuzen würden. Also kann einer von ihnen ausgelassen werden: Die Antwort lautet max(lcs(i+1, j), lcs(i, j+1)). Wenn eines der Suffixe leer ist, gibt es nichts Gemeinsames und die Antwort ist 0.

Das Verfahren ist langsam, weil bei jeder Nichtübereinstimmung zwei Aufrufe gestartet werden. Wenn die Zeichenketten keinen gemeinsamen Buchstaben haben, liegt bei jedem Aufruf eine Nichtübereinstimmung vor, bis eine Zeichenkette aufgebraucht ist, und die Anzahl der Aufrufe wächst wie die Anzahl der Möglichkeiten, die beiden Zeichenketten miteinander zu verschachteln. Bei zwei Zeichenketten mit jeweils 20 Buchstaben sind das etwa 2.8 × 10^11 Aufrufe; die großen Tests enthalten jeweils 1000 Buchstaben. Es gibt jedoch nur (n+1) × (m+1) verschiedene Paare (i, j), daher wiederholen fast alle Aufrufe einen früheren.

Zustand. Sei dp[i][j] die längste gemeinsame Teilsequenz der ersten i Buchstaben von text1 und der ersten j Buchstaben von text2. Bei Präfixen kann der Index 0 für eine leere Zeichenfolge stehen.

Rekurrenz. Vergleiche die letzten Buchstaben der beiden Präfixe, text1[i-1] und text2[j-1]. Sind sie gleich, ordne sie einander zu: dp[i][j] = dp[i-1][j-1] + 1. Andernfalls lass einen von ihnen weg: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Das ist dieselbe Überlegung wie bei der Rekursion, nur vom Ende aus gelesen. Basisfall: Zeile 0 und Spalte 0 enthalten den Wert 0, denn ein leeres Präfix hat nichts mit irgendeinem anderen gemeinsam. Reihenfolge: Jede Zelle liest die Zelle darüber, die Zelle links davon und die diagonal links oben, daher sind diese beim Ausfüllen Zeile für Zeile von links nach rechts immer bereits ausgefüllt. Die Antwort ist dp[n][m].

Für pear und reap lautet die Zeile für pea [0, 0, 1, 2, 2]. Der Wert ihrer Zelle für rea ist 2, weil a mit a übereinstimmt. Daher ist er gleich dem Wert der Zelle für pe und re, 1, plus eins. In der letzten Zelle werden bei pear und reap r und p verglichen, die unterschiedlich sind; deshalb wird der größere Wert der beiden benachbarten Zellen übernommen, also 2.

Die Tabelle hat (n+1) × (m+1) Zellen, und für jede ist ein konstanter Aufwand erforderlich: etwa 10^6 Schritte für zwei Zeichenfolgen mit je 1000 Buchstaben. Eine memoisierten Version der Rekursion füllt dieselben Zellen aus, rekursiert aber bis zu einer Tiefe von n + m Aufrufen, wodurch der standardmäßige Aufrufstapel in Sprachen wie Python überläuft.

Zeile i der Tabelle liest nur Zeile i-1 und ihre eigenen früheren Zellen. Sobald eine Zeile fertig ist, wird keine Zeile darüber jemals wieder gelesen. Verwende also zwei Arrays: prev für die fertige Zeile und cur für die gerade ausgefüllte Zeile, und vertausche sie nach jeder Zeile. Die Rekurrenz und die Reihenfolge bleiben genau gleich.

Eine gemeinsame Teilsequenz zweier Zeichenketten hängt nicht davon ab, welche Zeichenkette zuerst kommt. Daher kannst du sie vertauschen und die Zeilen entlang der kürzeren Zeichenkette laufen lassen. Jede Zeile enthält dann min(n, m) + 1 Zahlen: 1001 statt einer Million Zellen für die größten Eingaben, bei derselben Anzahl von 10^6 Arbeitsschritten.

Der erste Eintrag jeder Zeile steht für ein leeres Präfix der kürzeren Zeichenkette und muss daher 0 bleiben. Die Antwort ist der letzte Eintrag der letzten fertigen Zeile.