Longest Common Subsequence & the Survival Score
In short: the longest common subsequence (LCS) of two sequences is the
longest list of items that appear in both, in the same order, but not
necessarily side by side. A two-dimensional table, table[i][j] = the LCS
length of the first i items of a and the first j items of b, fills by
comparing the last item of each prefix: a match extends the diagonal by one, a
miss carries the larger of the cell above or to the left. The bottom-right
cell is the answer, and the diagonal steps taken to get there spell out the
subsequence itself.
Quarry keeps every revision of every document. When someone opens the history panel, the first question is simple: how much of the old version survived into the new one? A new paragraph in the middle shouldn't count as "everything after it changed", and a moved sentence shouldn't count as nothing changed. The measure that gets this right is the longest common subsequence (LCS): the longest list of lines that appear in both versions in the same order, not necessarily side by side.
This lesson fills the first real two-dimensional DP table in the course. Every diff you have ever read came out of a table like this one.
Why position-by-position fails
The obvious comparison lines the two versions up by index:
old = ["title", "intro", "body", "outro"]
new = ["title", "note", "intro", "body", "outro"]
same = sum(1 for a, b in zip(old, new) if a == b)
print(same)A subsequence ignores position and keeps order. title, intro, body, outro
appears in both lists in that order, so the survival count should be 4.
The recurrence
Let a and b be the two sequences. Define one cell:
table[i][j]= the LCS length of the firstiitems ofaand the firstjitems ofb.
Look at the last item of each prefix, a[i-1] and b[j-1].
- They match. Then that item can end the common subsequence, and the rest
is the best answer for both prefixes without it:
table[i-1][j-1] + 1. - They don't. Then at least one of the two can't be the last item of the
common subsequence. Either drop
a's last item or dropb's, and keep whichever is better:max(table[i-1][j], table[i][j-1]).
Row 0 and column 0 compare against an empty prefix, so they are all 0. Every cell depends on the cell above, the cell to the left and the diagonal, so filling row by row, left to right, always has the inputs ready.
Letters stand in for lines here, because they fit in a picture. Rows are
CRATE, columns are TRACE. Watch the arrows: a diagonal arrow at a match, and
a straight arrow from the larger neighbour otherwise.
A match copies the diagonal plus one. A miss takes the larger of up and left. The bottom-right cell is the LCS length.
Row 0 and column 0 compare against an empty prefix, so they are all 0 before any work starts. 6 by 6 table. At row 0, column 0 — value 0. 11 of 36 cells filled.
Filling m × n cells at constant work each costs O(m · n) time and, with
the full table, O(m · n) space. Brute force would compare each of the 2ᵐ
subsequences of a against b.
Step through the fill for two tiny words and watch which branch each cell takes:
Order matters, even when the items are the same:
def lcs(a, b):
t = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
for i in range(1, len(a) + 1):
for j in range(1, len(b) + 1):
if a[i - 1] == b[j - 1]:
t[i][j] = t[i - 1][j - 1] + 1
else:
t[i][j] = max(t[i - 1][j], t[i][j - 1])
return t[-1][-1]
print(lcs("RAT", "TAR"))Here is a version that gets the miss case wrong:
A and B survive from AXB into AB, so the answer is 2, but this prints 1. Fix the miss case.
❓ Cross-question: "Isn't this the longest common substring?" No. A substring must be contiguous, and one inserted line breaks it. For
"title, intro, body"against"title, note, intro, body", the longest common run of adjacent lines is 2 (intro, body), while the LCS is 3. The substring version has its own table, where a miss resets the cell to 0 instead of carrying the best neighbour.
Your own fill, drawn
Change the two strings and run it. The table redraws from your own loop, with
the letters of a down the side and b across the top. Try two identical
words, a word against its reverse, and a word against an empty string.
Your own table, cell by cell. The first row and column are the two words; the corner is the LCS length.
Why brute force was never an option
Brute force checks all 2ᵏ subsequences of a k-line document, while the table has about k² cells:
| lines k | subsequences (2ᵏ) | table cells (k²) |
|---|---|---|
| 10 | 1,024 | 100 |
| 20 | 1,048,576 | 400 |
| 30 | 1,073,741,824 | 900 |
Twenty lines already pass a million subsequences. A real file has thousands of lines, so brute force is out of reach and the table is the only option.
Idioms & real-world patterns
A similarity score
LCS length alone depends on document size. Dividing by the average length turns
it into a score between 0 and 1: 2 · common / (len(old) + len(new)). Two
identical versions score 1, and two versions with nothing in common score 0.
That's the survival score you're about to build, and Python's own difflib
reports a ratio of the same shape.
Sequences of anything
Nothing in the recurrence cares what the items are. Letters, lines, words,
tokens and records all work, as long as == means "the same item". Quarry
compares lines. A spelling checker compares letters. A version-control merge
compares lines from three files, and the capstone exercise below adds that third
dimension.
⚡ Advanced: one row is enough for the length
Each row reads only the row above it. Keep two rows and the memory drops from O(m · n) to O(n). The price is that the table is gone, and with it every arrow you'd need to recover which lines are common. Lesson 3 makes that trade explicit, and lesson 4 gets the lines back without paying for the whole table.
⚡ Advanced: shortest common supersequence
The shortest sequence that contains both a and b as subsequences writes
every shared item once: len(a) + len(b) − LCS. The build exercise is that
formula, and it's a common interview disguise for LCS.
Quick practice
def lcs_len(a, b):
t = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
for i in range(1, len(a) + 1):
for j in range(1, len(b) + 1):
if a[i - 1] == b[j - 1]:
t[i][j] = t[i - 1][j - 1] + 1
else:
t[i][j] = max(t[i - 1][j], t[i][j - 1])
return t[-1][-1]
print(lcs_len("AGCAT", "GAC"))IndexErrorThis crashes with IndexError before it can print anything. The LCS of "cat" and "cot" is "ct", length 2. Fix the two indices.
🎯 Your turn
Write similarity(old, new). Both are lists of lines. Return
{"common": k, "score": s}, where k is the LCS length and
s = 2 · k / (len(old) + len(new)), rounded to 3 decimal places. Two empty
versions are identical, so they score 1.0.
similarity(["title", "intro", "body", "outro"], ["title", "note", "intro", "body", "outro"])→{"common": 4, "score": 0.889}similarity([], [])→{"common": 0, "score": 1.0}
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green means this piece of the app is built. ✅