Longest Common Substring

Q: Wie hoch ist die Zeitkomplexität des längsten gemeinsamen Teilstrings?

Die Lösung mit dynamischer Programmierung benötigt O(n × m) Zeit und mit einer einzelnen Zeile O(m) Speicher. Die Erweiterung von jedem Startpaar aus benötigt im schlimmsten Fall O(n × m × min(n, m)) . Ein Suffixautomat erreicht etwa O(n + m) , allerdings auf Kosten eines deutlich längeren Programms.

Q: Wie gibst du die längste gemeinsame Teilzeichenfolge selbst zurück?

Immer wenn eine Zelle best übertrifft, speichere auch die Position i in s1 , an der dieser Block endet. Am Ende besteht die Teilzeichenfolge aus den best Buchstaben von s1 , die dort enden. Ein strikter Größer-als-Vergleich behält den ersten längsten Block bei, der in s1 gefunden wurde.

MittelDynamische Programmierung

+10

Du erhältst zwei Zeichenfolgen, s1 und s2. Eine Teilzeichenfolge ist eine zusammenhängende Folge von Buchstaben, die einer Zeichenfolge entnommen wird, zum Beispiel ork aus clockwork. Finde die längste Teilzeichenfolge, die s1 und s2 gemeinsam haben, und gib ihre Länge zurück. Wenn kein Buchstabe in beiden Zeichenfolgen vorkommt, lautet die Antwort 0.

Funktion

longestCommonSubstring(s1: string, s2: string) → integer

s1string: die erste Zeichenkette
s2string: die zweite Zeichenkette
Gibt zurückinteger: die Länge des längsten Buchstabenblocks, der in beiden Zeichenfolgen vorkommt

Einschränkungen

1 ≤ s1.length ≤ 1000
1 ≤ s2.length ≤ 1000
s1 und s2 bestehen aus Kleinbuchstaben des englischen Alphabets.

Beispiele

Eingabe: s1 = "clockwork"s2 = "workshop"
Ausgabe: 4
Erklärung: work steht am Ende von clockwork und am Anfang von workshop. Daher ist es eine gemeinsame Teilzeichenfolge der Länge 4, und kein längerer Block kommt in beiden vor.

Eingabe: s1 = "hammer"s2 = "harmed"
Ausgabe: 2
Erklärung: ha und me kommen in beiden Wörtern vor, aber keine Folge aus drei Buchstaben. Beide Wörter enthalten h, a, m, e in dieser Reihenfolge, aber in harmed steht ein r zwischen dem a und dem m.

Weiterführende Frage

Kannst du mit einem rollierenden Hash in etwa O(n + m) Zeit testen, ob es eine gemeinsame Teilzeichenfolge der Länge L gibt, und anschließend eine binäre Suche über L durchführen?

Tipps

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

0 von 3 geöffnet

Lösung

Ein Match von jedem Startpaar aus zu verlängern, liest dieselben Buchstaben erneut. Betrachte stattdessen, wo ein Block endet: Der gemeinsame Block, der bei s1[i] und s2[j] endet, ist um einen Buchstaben länger als derjenige, der bei den beiden jeweils vorherigen Buchstaben endet, oder leer, wenn die Buchstaben unterschiedlich sind. Eine Tabelle mit diesen Längen liefert die Antwort in O(n × m)-Zeit.

Von jedem Paar von Startpositionen aus erweitern

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

Idee

Jede gemeinsame Teilzeichenfolge beginnt an einer Position i von s1 und einer Position j von s2. Gehe für jedes Paar vorwärts, solange die Buchstaben übereinstimmen, und zähle die Schritte; die größte Anzahl ist die Antwort.

Bei sich wiederholendem Text werden die Durchläufe lang. Wenn beide Zeichenfolgen aus 1000 Wiederholungen von a bestehen, geht jeder Durchlauf bis zum Ende des kürzeren Suffixes: etwa 3.3 × 10^8 Buchstabenvergleiche. Der Durchlauf von (i, j) wiederholt den gesamten Durchlauf von (i+1, j+1), nur um einen Buchstaben versetzt.

Algorithmus

Setze best = 0.
Setze für jedes i in s1 und jedes j in s2 k = 0.
Solange sich sowohl i+k als auch j+k innerhalb ihrer Zeichenfolgen befinden und s1[i+k] == s2[j+k] gilt, erhöhe k um 1.
Behalte den größten Wert von k in best und gib ihn zurück.

def longestCommonSubstring(s1, s2):
    n, m = len(s1), len(s2)
    best = 0
    for i in range(n):
        for j in range(m):
            # Walk forward while the two strings agree
            k = 0
            while i + k < n and j + k < m and s1[i + k] == s2[j + k]:
                k += 1
            if k > best:
                best = k
    return best

Tabelle der Blocklängen, die bei jedem Paar enden

Idee

Sei run[i][j] die Länge des längsten gemeinsamen Blocks, der genau bei s1[i-1] und s2[j-1] endet; Zeile 0 und Spalte 0 enthalten 0. Ein solcher Block muss beide Buchstaben enthalten. Sind sie verschieden, gibt es keinen Block und die Zelle ist 0. Stimmen sie überein, besteht der Block aus diesem Buchstabenpaar plus dem Block, der jeweils einen Buchstaben früher in beiden Zeichenfolgen endet: run[i-1][j-1] + 1. Jeder gemeinsame Teilstring endet irgendwo, daher ist die Antwort die größte Zelle, ganz gleich, wo sie sich befindet.

Bei hammer und harmed ergeben die h jeweils 1 und die a verlängern den Block auf 2, dann unterbricht das r den Block. Das zweite m von hammer trifft auf das m von harmed, nachdem m und r nicht übereingestimmt haben, also beginnt es bei 1, und die e erhöhen den Wert auf 2. Keine Zelle erreicht 3.

Ein Vergleich pro Zelle: etwa eine Million bei zwei Zeichenfolgen mit jeweils 1000 Buchstaben, unabhängig vom Text.

Algorithmus

Initialisiere run mit n+1 Zeilen und m+1 Spalten, alle mit 0, und setze best = 0.
Durchlaufe i von 1 bis n und innerhalb davon j von 1 bis m, wobei du s1[i-1] mit s2[j-1] vergleichst.
Bei einer Übereinstimmung setze run[i][j] = run[i-1][j-1] + 1 und aktualisiere best.
Bei einer Nichtübereinstimmung belasse die Zelle bei 0.
Gib best zurück.

def longestCommonSubstring(s1, s2):
    n, m = len(s1), len(s2)
    # run[i][j]: length of the longest block that ends at s1[i-1] and at s2[j-1]
    run = [[0] * (m + 1) for _ in range(n + 1)]
    best = 0
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if s1[i - 1] == s2[j - 1]:
                run[i][j] = run[i - 1][j - 1] + 1
                if run[i][j] > best:
                    best = run[i][j]
            # a mismatch leaves run[i][j] at 0
    return best

Eine Zeile, von rechts nach links aktualisiert

Idee

Jede Zelle liest nur die Zelle diagonal links oben aus. Daher kann ein Array run mit m+1 Zahlen die Tabelle aufnehmen, wenn du j von rechts nach links durchläufst: Wenn du run[j] schreibst, enthält der Platz run[j-1] noch den Wert für den vorherigen Buchstaben von s1, also den Wert der diagonalen Zelle.

Bei einer Nichtübereinstimmung muss jetzt ausdrücklich 0 geschrieben werden, da der Platz noch eine Zahl aus der vorherigen Zeile enthält. Die Laufzeit bleibt O(n × m), und der Speicherbedarf sinkt von etwa 10^6 Zahlen auf 1001.

Algorithmus

Erstelle ein Array run mit m+1 Nullen und setze best = 0.
Gehe für jeden Buchstaben ch von s1 die Werte für j von m abwärts bis 1 durch.
Wenn ch == s2[j-1] gilt, setze run[j] = run[j-1] + 1 und aktualisiere best.
Andernfalls setze run[j] = 0.
Gib best zurück.

def longestCommonSubstring(s1, s2):
    m = len(s2)
    # run[j]: length of the common block that ends at the current letter of s1 and at s2[j-1]
    run = [0] * (m + 1)
    best = 0
    for ch in s1:
        # Right to left, so run[j-1] still holds the value from the previous letter of s1
        for j in range(m, 0, -1):
            if ch == s2[j - 1]:
                run[j] = run[j - 1] + 1
                if run[j] > best:
                    best = run[j]
            else:
                run[j] = 0
    return best

Stolperfallen und Grenzfälle

Die letzte Zelle zurückgeben. run[n][m] berücksichtigt nur Blöcke, die bei beiden letzten Buchstaben enden. Für abc und abd ist der Wert 0, während ab den Wert 2 ergibt.
Bei einer Nichtübereinstimmung den größeren Nachbarwert übernehmen. Das ist die Regel für Teilfolgen und ermöglicht es einem Block, Buchstaben zu überspringen: Bei hammer und harmed ergibt sich der Wert 4 statt 2.
Die einzelne Zeile von links nach rechts durchlaufen. Der diagonale Wert wird überschrieben, bevor du ihn liest, sodass a im Vergleich mit aa den Wert 2 ergibt.
Beim Verwenden der einzelnen Zeile das Zurücksetzen auslassen. Eine Länge vom vorherigen Buchstaben von s1 bleibt erhalten und verlängert später einen Block, den es dort gar nicht gibt.
Die Brute-Force-Methode ohne Prüfung der Grenzen durchlaufen. Bei zzzz im Vergleich mit zz wird hinter das Ende der kürzeren Zeichenkette gelesen.

Häufige Fragen3

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

Ein Teilstring ist eine zusammenhängende Folge von Buchstaben; eine Teilsequenz behält die Reihenfolge bei, kann aber Lücken lassen. Für hammer und harmed hat der längste gemeinsame Teilstring die Länge 2 und die längste gemeinsame Teilsequenz die Länge 4 (hame). In den Tabellen setzt eine Nichtübereinstimmung die Teilstringzelle auf 0 zurück, während die Teilsequenzzelle den größeren ihrer Nachbarn übernimmt.

Wie hoch ist die Zeitkomplexität des längsten gemeinsamen Teilstrings?

Die Lösung mit dynamischer Programmierung benötigt O(n × m) Zeit und mit einer einzelnen Zeile O(m) Speicher. Die Erweiterung von jedem Startpaar aus benötigt im schlimmsten Fall O(n × m × min(n, m)). Ein Suffixautomat erreicht etwa O(n + m), allerdings auf Kosten eines deutlich längeren Programms.

Wie gibst du die längste gemeinsame Teilzeichenfolge selbst zurück?

Immer wenn eine Zelle best übertrifft, speichere auch die Position i in s1, an der dieser Block endet. Am Ende besteht die Teilzeichenfolge aus den best Buchstaben von s1, die dort enden. Ein strikter Größer-als-Vergleich behält den ersten längsten Block bei, der in s1 gefunden wurde.

def longestCommonSubstring(s1, s2):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argumente

s1 = "clockwork"
s2 = "workshop"

Erwartete Ausgabe

Longest Common Substring

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Von jedem Paar von Startpositionen aus erweitern

Tabelle der Blocklängen, die bei jedem Paar enden

Eine Zeile, von rechts nach links aktualisiert

Stolperfallen und Grenzfälle

Häufige Fragen3

Ähnliche Aufgaben