String DP
Line one string down the side and the other along the top. Cell (i, j) answers the question for the first i letters against the first j. Every cell needs only its diagonal, the cell above and the cell to the left, so filling row by row always has them ready. LCS, edit distance and longest common substring are the same table with three different rules.
Longest common substring of "abcdxyz" and "xyzabcd", contiguous this time. Cell (i, j) is the length of the common run ending exactly at those two letters, so any mismatch resets it to 0.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 49, with their answers.
'a' vs 'x'. Diagonal is 0, above 0, left 0. What goes in (1, 1)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'a' vs 'y'. Diagonal is 0, above 0, left 0. What goes in (1, 2)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'a' vs 'z'. Diagonal is 0, above 0, left 0. What goes in (1, 3)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'a' vs 'a'. Diagonal is 0, above 0, left 0. What goes in (1, 4)?
Answer: 1. A match extends the run ending at the diagonal by one.
'a' vs 'b'. Diagonal is 0, above 0, left 1. What goes in (1, 5)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'a' vs 'c'. Diagonal is 0, above 0, left 0. What goes in (1, 6)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'a' vs 'd'. Diagonal is 0, above 0, left 0. What goes in (1, 7)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'b' vs 'x'. Diagonal is 0, above 0, left 0. What goes in (2, 1)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'b' vs 'y'. Diagonal is 0, above 0, left 0. What goes in (2, 2)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'b' vs 'z'. Diagonal is 0, above 0, left 0. What goes in (2, 3)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'b' vs 'a'. Diagonal is 0, above 1, left 0. What goes in (2, 4)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'b' vs 'b'. Diagonal is 1, above 0, left 0. What goes in (2, 5)?
Answer: 2. A match extends the run ending at the diagonal by one.
'b' vs 'c'. Diagonal is 0, above 0, left 2. What goes in (2, 6)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'b' vs 'd'. Diagonal is 0, above 0, left 0. What goes in (2, 7)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'c' vs 'x'. Diagonal is 0, above 0, left 0. What goes in (3, 1)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'c' vs 'y'. Diagonal is 0, above 0, left 0. What goes in (3, 2)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'c' vs 'z'. Diagonal is 0, above 0, left 0. What goes in (3, 3)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'c' vs 'a'. Diagonal is 0, above 0, left 0. What goes in (3, 4)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'c' vs 'b'. Diagonal is 0, above 2, left 0. What goes in (3, 5)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'c' vs 'c'. Diagonal is 2, above 0, left 0. What goes in (3, 6)?
Answer: 3. A match extends the run ending at the diagonal by one.
'c' vs 'd'. Diagonal is 0, above 0, left 3. What goes in (3, 7)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'd' vs 'x'. Diagonal is 0, above 0, left 0. What goes in (4, 1)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'd' vs 'y'. Diagonal is 0, above 0, left 0. What goes in (4, 2)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'd' vs 'z'. Diagonal is 0, above 0, left 0. What goes in (4, 3)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'd' vs 'a'. Diagonal is 0, above 0, left 0. What goes in (4, 4)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'd' vs 'b'. Diagonal is 0, above 0, left 0. What goes in (4, 5)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'd' vs 'c'. Diagonal is 0, above 3, left 0. What goes in (4, 6)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'd' vs 'd'. Diagonal is 3, above 0, left 0. What goes in (4, 7)?
Answer: 4. A match extends the run ending at the diagonal by one.
'x' vs 'x'. Diagonal is 0, above 0, left 0. What goes in (5, 1)?
Answer: 1. A match extends the run ending at the diagonal by one.
'x' vs 'y'. Diagonal is 0, above 0, left 1. What goes in (5, 2)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'x' vs 'z'. Diagonal is 0, above 0, left 0. What goes in (5, 3)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'x' vs 'a'. Diagonal is 0, above 0, left 0. What goes in (5, 4)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'x' vs 'b'. Diagonal is 0, above 0, left 0. What goes in (5, 5)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'x' vs 'c'. Diagonal is 0, above 0, left 0. What goes in (5, 6)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'x' vs 'd'. Diagonal is 0, above 4, left 0. What goes in (5, 7)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'y' vs 'x'. Diagonal is 0, above 1, left 0. What goes in (6, 1)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'y' vs 'y'. Diagonal is 1, above 0, left 0. What goes in (6, 2)?
Answer: 2. A match extends the run ending at the diagonal by one.
'y' vs 'z'. Diagonal is 0, above 0, left 2. What goes in (6, 3)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'y' vs 'a'. Diagonal is 0, above 0, left 0. What goes in (6, 4)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'y' vs 'b'. Diagonal is 0, above 0, left 0. What goes in (6, 5)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'y' vs 'c'. Diagonal is 0, above 0, left 0. What goes in (6, 6)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'y' vs 'd'. Diagonal is 0, above 0, left 0. What goes in (6, 7)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'z' vs 'x'. Diagonal is 0, above 0, left 0. What goes in (7, 1)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'z' vs 'y'. Diagonal is 0, above 2, left 0. What goes in (7, 2)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'z' vs 'z'. Diagonal is 2, above 0, left 0. What goes in (7, 3)?
Answer: 3. A match extends the run ending at the diagonal by one.
'z' vs 'a'. Diagonal is 0, above 0, left 3. What goes in (7, 4)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'z' vs 'b'. Diagonal is 0, above 0, left 0. What goes in (7, 5)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'z' vs 'c'. Diagonal is 0, above 0, left 0. What goes in (7, 6)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
'z' vs 'd'. Diagonal is 0, above 0, left 0. What goes in (7, 7)?
Answer: 0. The run is contiguous, so a mismatch ends it: 0.
How it runs, step by step
Longest common substring of "abcdxyz" and "xyzabcd", contiguous this time. Cell (i, j) is the length of the common run ending exactly at those two letters, so any mismatch resets it to 0.
Building the common-substring table for abcdxyz and xyzabcd. Row 0 and column 0 are the base cases.
(1, 1): 'a' against 'x'. Different letters, so no common run ends here: 0.
Cell 1, 1 compares a with x and becomes 0.
(1, 2): 'a' against 'y'. Different letters, so no common run ends here: 0.
Cell 1, 2 compares a with y and becomes 0.
(1, 3): 'a' against 'z'. Different letters, so no common run ends here: 0.
Cell 1, 3 compares a with z and becomes 0.
(1, 4): 'a' against 'a'. They match, so the run grows: diagonal 0 + 1 = 1.
Cell 1, 4 compares a with a and becomes 1.
(1, 5): 'a' against 'b'. Different letters, so no common run ends here: 0.
Cell 1, 5 compares a with b and becomes 0.
(1, 6): 'a' against 'c'. Different letters, so no common run ends here: 0.
Cell 1, 6 compares a with c and becomes 0.
(1, 7): 'a' against 'd'. Different letters, so no common run ends here: 0.
Cell 1, 7 compares a with d and becomes 0.
(2, 1): 'b' against 'x'. Different letters, so no common run ends here: 0.
Cell 2, 1 compares b with x and becomes 0.
(2, 2): 'b' against 'y'. Different letters, so no common run ends here: 0.
Cell 2, 2 compares b with y and becomes 0.
(2, 3): 'b' against 'z'. Different letters, so no common run ends here: 0.
Cell 2, 3 compares b with z and becomes 0.
(2, 4): 'b' against 'a'. Different letters, so no common run ends here: 0.
Cell 2, 4 compares b with a and becomes 0.
(2, 5): 'b' against 'b'. They match, so the run grows: diagonal 1 + 1 = 2.
Cell 2, 5 compares b with b and becomes 2.
(2, 6): 'b' against 'c'. Different letters, so no common run ends here: 0.
Cell 2, 6 compares b with c and becomes 0.
(2, 7): 'b' against 'd'. Different letters, so no common run ends here: 0.
Cell 2, 7 compares b with d and becomes 0.
(3, 1): 'c' against 'x'. Different letters, so no common run ends here: 0.
Cell 3, 1 compares c with x and becomes 0.
(3, 2): 'c' against 'y'. Different letters, so no common run ends here: 0.
Cell 3, 2 compares c with y and becomes 0.
(3, 3): 'c' against 'z'. Different letters, so no common run ends here: 0.
Cell 3, 3 compares c with z and becomes 0.
(3, 4): 'c' against 'a'. Different letters, so no common run ends here: 0.
Cell 3, 4 compares c with a and becomes 0.
(3, 5): 'c' against 'b'. Different letters, so no common run ends here: 0.
Cell 3, 5 compares c with b and becomes 0.
(3, 6): 'c' against 'c'. They match, so the run grows: diagonal 2 + 1 = 3.
Cell 3, 6 compares c with c and becomes 3.
(3, 7): 'c' against 'd'. Different letters, so no common run ends here: 0.
Cell 3, 7 compares c with d and becomes 0.
(4, 1): 'd' against 'x'. Different letters, so no common run ends here: 0.
Cell 4, 1 compares d with x and becomes 0.
(4, 2): 'd' against 'y'. Different letters, so no common run ends here: 0.
Cell 4, 2 compares d with y and becomes 0.
(4, 3): 'd' against 'z'. Different letters, so no common run ends here: 0.
Cell 4, 3 compares d with z and becomes 0.
(4, 4): 'd' against 'a'. Different letters, so no common run ends here: 0.
Cell 4, 4 compares d with a and becomes 0.
(4, 5): 'd' against 'b'. Different letters, so no common run ends here: 0.
Cell 4, 5 compares d with b and becomes 0.
(4, 6): 'd' against 'c'. Different letters, so no common run ends here: 0.
Cell 4, 6 compares d with c and becomes 0.
(4, 7): 'd' against 'd'. They match, so the run grows: diagonal 3 + 1 = 4.
Cell 4, 7 compares d with d and becomes 4.
(5, 1): 'x' against 'x'. They match, so the run grows: diagonal 0 + 1 = 1.
Cell 5, 1 compares x with x and becomes 1.
(5, 2): 'x' against 'y'. Different letters, so no common run ends here: 0.
Cell 5, 2 compares x with y and becomes 0.
(5, 3): 'x' against 'z'. Different letters, so no common run ends here: 0.
Cell 5, 3 compares x with z and becomes 0.
(5, 4): 'x' against 'a'. Different letters, so no common run ends here: 0.
Cell 5, 4 compares x with a and becomes 0.
(5, 5): 'x' against 'b'. Different letters, so no common run ends here: 0.
Cell 5, 5 compares x with b and becomes 0.
(5, 6): 'x' against 'c'. Different letters, so no common run ends here: 0.
Cell 5, 6 compares x with c and becomes 0.
(5, 7): 'x' against 'd'. Different letters, so no common run ends here: 0.
Cell 5, 7 compares x with d and becomes 0.
(6, 1): 'y' against 'x'. Different letters, so no common run ends here: 0.
Cell 6, 1 compares y with x and becomes 0.
(6, 2): 'y' against 'y'. They match, so the run grows: diagonal 1 + 1 = 2.
Cell 6, 2 compares y with y and becomes 2.
(6, 3): 'y' against 'z'. Different letters, so no common run ends here: 0.
Cell 6, 3 compares y with z and becomes 0.
(6, 4): 'y' against 'a'. Different letters, so no common run ends here: 0.
Cell 6, 4 compares y with a and becomes 0.
(6, 5): 'y' against 'b'. Different letters, so no common run ends here: 0.
Cell 6, 5 compares y with b and becomes 0.
(6, 6): 'y' against 'c'. Different letters, so no common run ends here: 0.
Cell 6, 6 compares y with c and becomes 0.
(6, 7): 'y' against 'd'. Different letters, so no common run ends here: 0.
Cell 6, 7 compares y with d and becomes 0.
(7, 1): 'z' against 'x'. Different letters, so no common run ends here: 0.
Cell 7, 1 compares z with x and becomes 0.
(7, 2): 'z' against 'y'. Different letters, so no common run ends here: 0.
Cell 7, 2 compares z with y and becomes 0.
(7, 3): 'z' against 'z'. They match, so the run grows: diagonal 2 + 1 = 3.
Cell 7, 3 compares z with z and becomes 3.
(7, 4): 'z' against 'a'. Different letters, so no common run ends here: 0.
Cell 7, 4 compares z with a and becomes 0.
(7, 5): 'z' against 'b'. Different letters, so no common run ends here: 0.
Cell 7, 5 compares z with b and becomes 0.
(7, 6): 'z' against 'c'. Different letters, so no common run ends here: 0.
Cell 7, 6 compares z with c and becomes 0.
(7, 7): 'z' against 'd'. Different letters, so no common run ends here: 0.
Cell 7, 7 compares z with d and becomes 0.
The longest common substring has length 4, the largest cell in the table. 64 cells, each from three neighbours: O(m x n).
The answer is 4.
Write it yourself
Define longestCommonSubsequence(a, b) and return the length of the longest subsequence both strings contain. It runs in your browser against this lesson's own 2 examples.
// Equal characters extend the diagonal by one; otherwise take the better of dropping one character from either string.function longestCommonSubsequence(a, b) { return 0;}
Remember
- Row 0 and column 0 are the empty prefix: the base cases. Edit distance counts up along them, the others hold 0.
- A match uses the diagonal. A mismatch reads above and left (LCS: max, edit distance: 1 + min of all three, substring: reset to 0).
- LCS and edit distance read the bottom-right cell. Longest common substring reads the largest cell anywhere.
Related
Where this is used
SearchFuzzy search in Lucene and Elasticsearch
A fuzzy query means match anything within edit distance 1 or 2 of this word, so the table is the definition of the query. Filling it against every term in the index would cost m x n per term, so Lucene does not: it compiles the query word into a Levenshtein automaton that accepts exactly the strings within distance k, then intersects that automaton with the finite state transducer holding the term dictionary. The table says what the answer is and the automaton is what makes it affordable over millions of terms, which is also why the edit distance ceiling is capped at 2.
DatabasesPostgreSQL fuzzystrmatch
The fuzzystrmatch extension exposes this table directly as levenshtein(a, b), with a variant that prices insertions, deletions and substitutions separately for domains where a dropped letter and a wrong letter are not equally likely. Because the function fills a whole rectangle for every pair of rows it touches, no index can short-circuit it and a query that levenshteins a large column is a full scan. That is why the extension also ships levenshtein_less_equal(a, b, max_d), which fills only a band around the diagonal and abandons the pair the moment the distance is known to exceed max_d.
Speech recognitionWord error rate for speech recognition
Recognisers are scored by word error rate, which is the edit distance between the reference transcript and what the system produced over the number of reference words, with each whole word treated as one symbol rather than each character. Walking the finished table backwards splits that single number into substitutions, insertions and deletions, which is what tells you whether a model is mishearing words or inventing them. NIST's sclite, the scorer behind decades of published benchmark numbers, is this alignment.
Developer toolsPython's difflib
difflib.SequenceMatcher, which backs unified_diff and the get_close_matches suggestions that many command line tools use for did you mean, works by finding the longest matching block between two sequences and then recursing on the parts to its left and right. That inner search is the longest common substring rule with one row kept: its j2len dictionary reads j2len[j - 1] + 1 on a hit, and a miss simply leaves the key absent, which is the reset to 0. Anchoring on the longest run is why its diffs read the way a person would have written them, even though the edit script it produces is not the shortest one.
Why it works this way
Why the table has an extra row and column
Row 0 and column 0 stand for the empty prefix, and they exist so the rules never have to ask whether a neighbour is off the table. dp[1][1] reads dp[0][0], a real cell meaning two empty strings, instead of a special case. The price is the offset that causes most of the bugs in this algorithm: dp[i][j] is about the first i characters, so the character it is deciding on is a[i - 1], not a[i]. Write a[i] and you are comparing the character after the one you meant, and at i = a.length you run off the end of the string entirely.
Why a mismatch resets to 0 for substring but takes a max for subsequence
A subsequence may skip characters, so a mismatch still leaves something to salvage: drop the last character of one string or of the other and keep the better of the two, which is max(above, left). A substring has to be contiguous, so a mismatch ends the run and nothing earlier can reach past it, which makes the cell 0. That is also why the two read their answers from different places: dp[m][n] is by definition the best run ending at the last character of both strings, which is rarely the best run anywhere.
Neighbouring cells differ by at most 1, and the fast versions live on that
In the edit distance table, any two cells that are side by side or stacked differ by at most 1, because one extra character can change the answer by at most one operation. Two things follow. On a match you can take the diagonal outright and skip the min, since neither dp[i - 1][j] + 1 nor dp[i][j - 1] + 1 can be smaller than dp[i - 1][j - 1]. And if you only care whether the distance is at most k, every cell that can still matter lies within k of the main diagonal, so you fill a band of 2k + 1 diagonals instead of the rectangle and the cost falls from m x n to roughly k x m. Bounded matchers such as PostgreSQL's levenshtein_less_equal are built on that second consequence.
Edit distance counts code units, not what the eye sees
The code indexes a String directly, so it compares whatever unit the language stores. In Kotlin, Java and JavaScript that is a UTF-16 code unit, so an emoji outside the basic plane counts as two and contributes phantom operations. Normalisation bites harder: the letter e with an acute accent as the single code point U+00E9, and the same letter as plain e followed by combining accent U+0301, render identically and come out two operations apart. If the strings come from users, normalise to NFC and iterate by code point, or by grapheme cluster when flags and skin tone emoji are in play, before the table ever sees them.
Read more
- Longest common subsequenceWikipedia
- Levenshtein distanceWikipedia
- Longest common substringWikipedia
- difflib, and the longest matching block it is built onPython docs · docs.python.org
- Edit DistanceCSES 1639 · cses.fi