Beim Longest Common Substring suchen wir die längste zusammenhängende Zeichenfolge, die in zwei Strings vorkommt.
Beispiel:
ABABC
BABCA
Der längste gemeinsame Substring lautet:
BABC
mit Länge 4.
Substring bedeutet zusammenhängend
Für:
ABCDE
sind beispielsweise:
ABC
BCD
DE
gültige Substrings.
ACE ist dagegen kein Substring, da die Zeichen nicht direkt nebeneinander stehen.
Dynamic Programming
Wir definieren:
dp[i][j]
als Länge des längsten gemeinsamen Substrings, der genau an a[i - 1] und b[j - 1] endet.
Wenn beide Zeichen gleich sind:
dp[i][j] = dp[i - 1][j - 1] + 1
Bei einem Unterschied:
dp[i][j] = 0
Der Wert wird auf null gesetzt, weil ein Substring ohne Unterbrechung zusammenhängend bleiben muss.
Beispiel
Für:
ABABC
BABCA
entsteht konzeptionell:
B A B C A
A 0 1 0 0 1
B 1 0 2 0 0
A 0 2 0 0 1
B 1 0 3 0 0
C 0 0 0 4 0
Der größte Wert ist 4.
TypeScript
function longestCommonSubstring(
a: string,
b: string
): string {
const dp = Array.from(
{ length: a.length + 1 },
() => new Array(b.length + 1).fill(0)
);
let maxLength = 0;
let endIndex = 0;
for (let i = 1; i <= a.length; i++) {
for (let j = 1; j <= b.length; j++) {
if (a[i - 1] === b[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
if (dp[i][j] > maxLength) {
maxLength = dp[i][j];
endIndex = i;
}
}
}
}
return a.slice(endIndex - maxLength, endIndex);
}
Komplexität
Für Stringlängen n und m gilt:
Time Complexity: O(n × m)
Space Complexity: O(n × m)
Da nur die vorherige Zeile benötigt wird, kann der Speicher auf:
O(min(n, m))
reduziert werden.
Unterschied zu Longest Common Subsequence
Beim Substring müssen alle Zeichen direkt nebeneinanderliegen.
Bei einer Subsequence muss lediglich die Reihenfolge erhalten bleiben.
Beispiel:
ABCDEF
ACEF
ACEF ist eine gemeinsame Subsequence, jedoch kein zusammenhängender Substring des ersten Strings.
Der wichtigste Unterschied im DP ist:
Mismatch bei Substring → 0
während LCS bei einem Mismatch Ergebnisse benachbarter Zustände weiterverwenden kann.
Anwendungen
Mögliche Anwendungen sind:
- String Similarity
- Data Cleaning
- CRM-Deduplizierung
- DNA-Sequenzanalyse
- Dokumentvergleich
- Versionsvergleich
- Log-Analyse
Eine lange gemeinsame Zeichenfolge kann beispielsweise ein Signal dafür sein, dass zwei CRM-Datensätze miteinander verwandt sind.
Mehrere optimale Lösungen
Es können mehrere Substrings mit gleicher maximaler Länge existieren.
Beispiel:
abcXYZ123
abcABC123
Sowohl abc als auch 123 haben Länge 3.
Typische Interviewfrage
Häufig wird verlangt, Länge oder Inhalt des längsten gemeinsamen Substrings zweier Strings zu bestimmen.
Entscheidend sind:
- zusammenhängende Zeichen
- passende DP-Definition
- Reset auf
0bei Mismatch - globales Maximum
O(n × m)Laufzeit
Fazit
Longest Common Substring findet die längste zusammenhängende gemeinsame Sequenz zweier Strings.
Die Kernregel lautet:
Match → dp[i - 1][j - 1] + 1
Mismatch → 0
Die klassische Dynamic-Programming-Lösung benötigt O(n × m) Zeit.