Longest Common Subsequence

Q: Wie hoch ist die Zeitkomplexität der längsten gemeinsamen Teilsequenz?

Die Tabellenlösung benötigt O(n × m) Zeit, eine Zelle pro Präfixpaar. Für die vollständige Tabelle benötigt sie O(n × m) Speicher oder mit zwei Zeilen O(min(n, m)) . Eine einfache Rekursion ohne Tabelle ist exponentiell.

MittelDynamische Programmierung

+10

Du erhältst zwei Zeichenfolgen, text1 und text2. Eine Teilsequenz einer Zeichenfolge behält einige ihrer Buchstaben in ihrer ursprünglichen Reihenfolge bei und lässt den Rest weg; die beibehaltenen Buchstaben müssen nicht nebeneinanderstehen. Gib die Länge der längsten Zeichenfolge zurück, die eine Teilsequenz beider Zeichenfolgen ist, oder 0, wenn die beiden Zeichenfolgen keinen Buchstaben gemeinsam haben.

Funktion

longestCommonSubsequence(text1: string, text2: string) → integer

text1string: die erste Zeichenkette
text2string: die zweite Zeichenfolge
Gibt zurückinteger: die Länge der längsten gemeinsamen Teilsequenz

Einschränkungen

1 ≤ text1.length ≤ 1000
1 ≤ text2.length ≤ 1000
Beide Zeichenketten enthalten ausschließlich englische Kleinbuchstaben.

Beispiele

Eingabe: text1 = "stone"text2 = "longest"
Ausgabe: 3
Erklärung: o, n und e kommen in beiden Wörtern in dieser Reihenfolge vor, also ist one gemeinsam, Länge 3. Die Buchstaben s und t stehen in longest zuletzt, aber in stone zuerst, daher ergibt ihre Verwendung höchstens st.

Eingabe: text1 = "pear"text2 = "reap"
Ausgabe: 2
Erklärung: ea kommt in beiden Wörtern vor. Das p und das r stehen in den beiden Wörtern auf gegenüberliegenden Seiten von ea, sodass sich keines davon damit verbinden kann, und die Antwort ist 2.

Weiterführende Frage

Kannst du eine längste gemeinsame Teilsequenz zusammen mit ihrer Länge zurückgeben?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Gieriges Matching scheitert: Wenn man das c von cab mit dem letzten c von abc paart, bleibt nichts für a und b übrig; überspringt man es, findet man ab. Die Antwort für zwei Präfixe hängt von den Antworten für kürzere Präfixe ab, daher löst eine Tabelle der Größe (n+1) × (m+1) jedes Paar genau einmal. Jede Zeile liest nur die Zeile darüber, daher reichen zwei Zeilen aus.

Vergleiche die ersten Buchstaben mit Rekursion

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Sei lcs(i, j) die Antwort für die Suffixe text1[i:] und text2[j:]. Wenn ihre ersten Buchstaben gleich sind, ordne sie einander zu: Eine längste gemeinsame Teilsequenz, die dieses Paar überspringt, 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 ihre Partner die Paare kreuzen lassen würden. Also kann einer von ihnen weggelassen werden: max(lcs(i+1, j), lcs(i, j+1)). Ein leeres Suffix ergibt 0.

Bei jeder Nichtübereinstimmung beginnen zwei Aufrufe. Zwei Zeichenketten mit 20 Buchstaben und ohne gemeinsame Buchstaben benötigen bereits etwa 2.8 × 10^11 Aufrufe, dabei gibt es nur (n+1) × (m+1) verschiedene Paare (i, j), sodass sich fast jeder Aufruf wiederholt.

Algorithmus

Schreibe lcs(i, j) für die Suffixe, die bei i und j beginnen.
Wenn i oder j hinter dem Ende seiner Zeichenkette liegt, gib 0 zurück.
Wenn text1[i] == text2[j], gib 1 + lcs(i+1, j+1) zurück.
Andernfalls gib max(lcs(i+1, j), lcs(i, j+1)) zurück.
Die Antwort ist lcs(0, 0).

def longestCommonSubsequence(text1, text2):
    def lcs(i, j):
        # The longest common subsequence of text1[i:] and text2[j:]
        if i == len(text1) or j == len(text2):
            return 0
        if text1[i] == text2[j]:
            return 1 + lcs(i + 1, j + 1)
        return max(lcs(i + 1, j), lcs(i, j + 1))

    return lcs(0, 0)

Fülle eine Tabelle mit Präfixen aus

Idee

Sei dp[i][j] die Antwort für die ersten i Buchstaben von text1 und die ersten j Buchstaben von text2, wobei Index 0 ein leeres Präfix bedeutet und Zeile 0 sowie Spalte 0 den Wert 0 haben. Vergleiche die letzten Buchstaben der beiden Präfixe, text1[i-1] und text2[j-1]: Sind die Buchstaben gleich, werden sie gepaart: dp[i-1][j-1] + 1; sind sie verschieden, lässt man einen von ihnen weg: max(dp[i-1][j], dp[i][j-1]). Das ist die Rekursion, vom Ende aus gelesen.

Jede Zelle liest die Zellen darüber, links davon und diagonal oben links, daher sind sie beim zeilenweisen Füllen von links nach rechts immer bereits berechnet. 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 und zum Wert der Zelle für pe und re eins hinzukommt.

Zwei Zeichenfolgen mit je 1000 Buchstaben benötigen etwa 10^6 Schritte mit konstanter Laufzeit.

Algorithmus

Erstelle eine Tabelle dp mit (n+1) × (m+1) Nullen.
Vergleiche für i von 1 bis n und j von 1 bis m text1[i-1] mit text2[j-1].
Bei einer Übereinstimmung setze dp[i][j] = dp[i-1][j-1] + 1.
Andernfalls setze dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
Gib dp[n][m] zurück.

def longestCommonSubsequence(text1, text2):
    n, m = len(text1), len(text2)
    # dp[i][j]: the longest common subsequence of text1[:i] and text2[:j].
    # Row 0 and column 0 stay 0: an empty prefix has nothing in common.
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[n][m]

Behalte nur zwei Zeilen

Idee

Sobald eine Zeile fertig ist, werden die darüberliegenden Zeilen nie wieder gelesen. Behalte prev für die fertige Zeile und cur für die Zeile, die gerade gefüllt wird, und tausche sie nach jeder Zeile. Die Rekurrenz und die Reihenfolge bleiben gleich.

Die Antwort hängt nicht davon ab, welche Zeichenfolge zuerst kommt, also lass die Zeilen entlang der kürzeren verlaufen. Jede Zeile enthält dann min(n, m) + 1 Zahlen: 1001 statt einer Million Zellen für die größten Eingaben, bei denselben 10^6 Schritten.

Algorithmus

Wenn text2 länger als text1 ist, vertausche sie.
Erstelle prev und cur, jeweils mit m + 1 Nullen, wobei m die kürzere Länge ist.
Fülle für jeden Buchstaben von text1 cur[1..m] nach derselben Regel wie in der Tabelle und lies dabei prev für die darüberliegende Zeile.
Vertausche prev und cur.
Gib prev[m] zurück.

def longestCommonSubsequence(text1, text2):
    if len(text2) > len(text1):
        text1, text2 = text2, text1  # keep the rows as short as the shorter string
    m = len(text2)
    # prev[j]: the answer for the previous prefix of text1 and text2[:j]
    prev = [0] * (m + 1)
    for ch in text1:
        cur = [0] * (m + 1)
        for j in range(1, m + 1):
            if ch == text2[j - 1]:
                cur[j] = prev[j - 1] + 1
            else:
                cur[j] = max(prev[j], cur[j - 1])
        prev = cur
    return prev[m]

Stolperfallen und Grenzfälle

Tabellenindizes mit Zeichenkettenindizes vermischen. Die Zelle dp[i][j] vergleicht text1[i-1] mit text2[j-1], weil Zeile 0 dem leeren Präfix entspricht.
Bei einer Übereinstimmung eins zu max(dp[i-1][j], dp[i][j-1]) addieren statt zu dp[i-1][j-1]. Dadurch kann ein Buchstabe zweimal verwendet werden: aa im Vergleich mit a würde 2 statt 1 ergeben.
In die Zeile schreiben, aus der du gerade liest. Bei zwei Zeilen muss jeder Wert aus der darüberliegenden Zeile aus prev stammen, und cur[0] muss 0 bleiben.
Die Rekursion in Python bei Zeichenketten mit 1000 Buchstaben mit Memoisierung versehen. Die Aufruftiefe erreicht 2000 und überschreitet damit den Standardgrenzwert von 1000.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität der längsten gemeinsamen Teilsequenz?

Die Tabellenlösung benötigt O(n × m) Zeit, eine Zelle pro Präfixpaar. Für die vollständige Tabelle benötigt sie O(n × m) Speicher oder mit zwei Zeilen O(min(n, m)). Eine einfache Rekursion ohne Tabelle ist exponentiell.

Was ist der Unterschied zwischen der längsten gemeinsamen Teilsequenz und der längsten gemeinsamen Teilzeichenfolge?

Eine Teilfolge darf Buchstaben überspringen, solange die Reihenfolge beibehalten wird; eine Teilzeichenfolge ist ein Block benachbarter Buchstaben. Für stone und longest ist die längste gemeinsame Teilfolge one (3), aber die längste gemeinsame Teilzeichenfolge ist on (2). Die Tabelle für Teilzeichenfolgen setzt eine Zelle bei einer Nichtübereinstimmung auf 0 zurück, statt den Wert eines Nachbarn zu übernehmen.

Wie hängt LCS mit Diff-Tools und der Editierdistanz zusammen?

Ein Diff zwischen zwei Versionen einer Datei behält die längste gemeinsame Teilsequenz ihrer Zeilen bei und zeigt jede andere Zeile als hinzugefügt oder entfernt an. Die geringste Anzahl an Einfügungen und Löschungen, die eine Zeichenfolge in die andere umwandelt, ist n + m - 2 × LCS. Die Editierdistanz erlaubt auch das Ersetzen eines Buchstabens, daher benötigt sie eine eigene Tabelle.

def longestCommonSubsequence(text1, text2):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argumente

text1 = "stone"
text2 = "longest"

Erwartete Ausgabe

Longest Common Subsequence

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Vergleiche die ersten Buchstaben mit Rekursion

Fülle eine Tabelle mit Präfixen aus

Behalte nur zwei Zeilen

Stolperfallen und Grenzfälle

Häufige Fragen3

Ähnliche Aufgaben