Längste gemeinsame Teilfolge
Richten Sie zwei Zeichenfolgen mit einer DP-Tabelle aus
Längste gemeinsame Teilfolge ist eine kostenlose Competitive Programming Academy-Lektion auf CoddyKit. Dies ist Lektion 3 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Competitive Programming Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Was eine Teilfolge ist
Eine Teilfolge behält die Reihenfolge der Zeichen bei, darf aber einige überspringen. Aus 'abcde' können Sie 'ace' bilden, aber niemals 'aec'.
Das LCS-Ziel
Bei zwei Zeichenketten ist die längste gemeinsame Teilfolge die längste Sequenz, die in beiden in derselben relativen Reihenfolge vorkommt.
Zum Gitter wechseln
Vergleichen Sie Präfixe der beiden Zeichenketten. Eine 2D-Tabelle über deren Längen verwandelt das Problem in eine vertraute Gitter-DP.
Zustand definieren
Sei dp[i][j] die Länge der LCS der ersten i Zeichen von A und der ersten j Zeichen von B.
Wenn Zeichen übereinstimmen
Wenn A[i-1] gleich B[j-1] ist, verlängert dieses gemeinsame Zeichen die LCS. Addieren Sie 1 zum diagonalen Wert dp[i-1][j-1].
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1] + 1Wenn sie sich unterscheiden
Wenn sich die Zeichen unterscheiden, lassen Sie ein Zeichen aus einer der beiden Zeichenketten weg und behalten das bessere Ergebnis. Sie nehmen das max der beiden Nachbarn.
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])Der Basisfall
Ein leeres Präfix hat nichts gemeinsam, daher ist die LCS-Länge null. Zeile 0 und Spalte 0 bleiben vollständig mit Nullen gefüllt.
dp = [[0] * (m+1) for _ in range(n+1)]Eine zusätzliche Zeile und Spalte
Wenn Sie die Tabelle mit der Größe n+1 mal m+1 anlegen, erhalten Sie einen kostenlosen Null-Rand. Dadurch entfallen lästige Bereichsprüfungen an den Kanten.
Tabelle ausfüllen
Durchlaufen Sie i und j aufsteigend ab 1. Jede Zelle benötigt nur die Werte oben, links und diagonal, die bereits berechnet sind.
for i in range(1, n+1):
for j in range(1, m+1):
...Länge ablesen
Die vollständige LCS-Länge steht in der Ecke. Die Antwort ist dp[n][m], sobald jede Zelle ausgefüllt ist.
length = dp[n][m]Komplexität
Sie besuchen jede Zelle genau einmal. Daher benötigen Laufzeit und Speicher O(n times m). Das reicht problemlos für Zeichenketten mit einigen Tausend Zeichen.
Schnelltest
Die aktuellen Zeichen A[i-1] und B[j-1] sind gleich. Welche Aktualisierung ist richtig?
Zusammenfassung: LCS
Erstellen Sie eine Tabelle der Größe n+1 mal m+1: Bei einer Übereinstimmung addieren Sie 1 zum diagonalen Wert, andernfalls nehmen Sie den größten Nachbarn. Die Ecke enthält die Länge. 🔗
Häufig gestellte Fragen
Ist die Lektion „Längste gemeinsame Teilfolge“ kostenlos?
Ja — der vollständige Text von „Längste gemeinsame Teilfolge“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Competitive Programming Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Längste gemeinsame Teilfolge“?
Richten Sie zwei Zeichenfolgen mit einer DP-Tabelle aus Du übst Competitive Programming Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Competitive Programming Academy zu starten?
Keine Vorkenntnisse erforderlich. Competitive Programming Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 3 von 4.
Wie lange dauert die Lektion „Längste gemeinsame Teilfolge“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Competitive Programming Academy-Lektion Code schreiben und ausführen?
Ja. Jede Competitive Programming Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Pfade in einem Raster zählen
- Minimale Pfadsumme mit Hindernissen
- Längste gemeinsame Teilfolge
- Editierdistanz Schritt für Schritt