Reconstruct the shared lineage of diverging strings by tracing optimal alignments across a DP table.
- Call the length of the longest shared sequence between two test strings before building the table
- Step the DPHeatmap to watch diagonal match rewards and horizontal/vertical skips build the score
- Take the boss round bet on how Hirschberg cuts quadratic space down to linear memory
After thisYou will master the diff engine inside Git, bioinformatics sequence alignment, and bit-parallel LCS.
Short on timeStep the DPHeatmap to trace the highlighted diagonal staircase that powers git diff.
The Surviving Thread
3 minthe hook
git diff decides which lines you added and which you deleted by measuring one number between the two files. The obvious method — list every subsequence and keep the longest shared one — is exponential. The prefix table that answers it is quadratic: 4,225 cells for two 64-character strings with distinct longest common subsequences.
Read the two strings as rows, and cross out characters until the survivors agree.
A B C B D A B
B D C A B A
The word BCAB survives in each: the top row keeps positions 2, 3, 4, 6, the bottom keeps 1, 3, 4, 5. Try to keep five characters and you stall at four.
How long is the longest common subsequence of ABCBDAB and BDCABA?
Four is a length, not a word. That gap runs the whole page: measuring the length is cheap, printing one word is cheap, and counting all the words is not.
Keep one picture: the staircase, a monotone path from the top-left corner of the prefix grid to the bottom-right. A diagonal step lands on a matching pair, a step down or right skips a character of one string. The staircase is the common subsequence, and its height is the length.
NextWhy does naive subsequence comparison require evaluating 2^32 candidate combinations?
The Naive Power-Set Trap
2 minthe trap
Operationally you are handed two strings, of length and of length , and asked for the longest word that is a subsequence — a selection of positions in order, not necessarily adjacent — of both. Brute force lists all subsequences of and keeps the longest that also sits in . That is exponential work for an answer that is one integer.
The working fix is dynamic. Let be the length of the longest common subsequence of the prefixes and :
That recurrence is correct, and it never mentions a subsequence. It compares prefixes and takes maxima. What it measures is a height in an order built from the two strings, and that order is the object we actually want.
NextHow does the two-dimensional dynamic programming grid trace the diagonal alignment path?
The Matching Cells
2 minthe invariant
Take the prefixes of in order: . Prefixes order by extension, so this is a chain — a totally ordered set — with elements. The prefixes of form a second chain with elements.
The product of the two chains is the grid of prefix pairs. Its element is the pair , and exactly when and . A product of two chains is a lattice, and this one — the grid — is the prefix lattice of the pair of strings.
Inside it sit the matching cells
carrying the same product order. A chain in is a set of pairwise comparable matching cells, meaning both rows and columns strictly increase.
Its cells pair with where every pair agrees, spelling a single common subsequence of length . Every common subsequence arises this way, so
the longest chain among the matching cells.
The DP table is this lattice with a label on every cell: is the height of inside the rectangle — the tallest chain reachable using only the first characters of and the first of . Hover a cell in section 4 and that height is the number you are reading.
NextHow did Hunt and McIlroy exploit sparse matching cells to build the PDP-11 Unix diff?
Decomposing the Monotone Staircase
2 minthe algebra
The Three-Way Choice at the Boundary
Fix a longest chain in the rectangle and inspect its last cell, the one with the largest row and column. Exactly one of three things holds.
- The last cell is , which needs . Everything before it lies in , so the chain has length .
- The last cell is not in row , so the chain already lives in and has length .
- The last cell is not in column , giving .
When the first case beats the other two, and when the cell is not in so only the last two remain. Those three cases are the recurrence above. The table is Wagner and Fischer 1974, written for string-to-string correction; the common subsequence is the case where substitution is forbidden.
Staircases as String Alignments
Draw the grid with the row index down and the column index across. A chain in is a sequence of cells visited without ever moving left or up.
Thread a path through them: step down to advance rows, or right to advance columns. Connecting to the first cell and the last cell to completes the route.
Every path from to built from down-steps, right-steps and diagonal steps is an alignment of the two strings.
- A down-step consumes one character of and none of — a deletion.
- A right-step consumes one character of and none of — an insertion.
- A diagonal step consumes one of each, and when it lands on a matching cell it is a matched pair.
Restrict the diagonal steps to matching cells and the correspondence is exact. Each such staircase picks out the diagonal cells , both coordinates increasing, each pair equal — a chain of and nothing more.
The staircase is the chain, and the chain is the common subsequence. Different staircases can spell the same word: aab and aba share ab along two different staircases. That gap between witnesses and words returns in the counting section below.
Read the table as a longest path and is the greatest number of match-diagonal steps on any staircase from to . The three cases of the recurrence are the three possible last moves, and the arrows that light up when you hover a cell are exactly those moves.
The Exact Duality with Edit Distance
Price a down-step and a right-step at one each, and a matching diagonal step at zero. A staircase from to with match-diagonal steps spends down-steps deleting the characters of it skips and right-steps inserting the characters of it adds, so its cost is
The cheapest staircase maximises , and the largest is . Therefore the insert/delete edit distance is
a derived identity, not a definition: it is the staircase cost above at . It is the same identity the edit distance page reaches from the other side, and it is the honest answer to the next prompt.
The quantity m + n − 2·LCS(a, b) is a distance between strings. Is it a metric? And is LCS itself a metric?
The swap between the two sides of the prompt is the lesson: distance is a metric because it prices a path, and LCS is not because it measures an overlap. Overlap does not add like distance.
One Number, Many Witnesses, Combinatorial Explosion
The height is one number, and the table computes it in time and space. Press Trace solution and the highlighted chain walks one witness out — a staircase of matched cells, one longest common subsequence you can print. Keeping the whole table to trace it costs memory; Hirschberg 1975 reconstructs the same witness in space by splitting the strings in half, computing the table from both ends, and recursing on the winning half.
Counting the distinct longest common subsequences is a different order of problem. Take distinct symbols and set
a = x₁ y₁ x₂ y₂ ⋯ x_k y_k
b = y₁ x₁ y₂ x₂ ⋯ y_k x_k
In the two symbols of each block appear one way round; in the other way. A common subsequence can use at most one symbol from any block — using both would need the two orders to agree.
Reaching the maximum length requires choosing exactly one symbol from each block. Every distinct set of choices yields a valid longest common subsequence, generating distinct words on strings of length .
1 minboss round
For a = 1234 and b = 2143 — the block-reversal family with k = 2 — how many distinct longest common subsequences are there?
One caution if you try to count. A DP that sums its predecessor counts counts staircases, not words, and the two differ: aab and aba reach the word ab by two different staircases, so a predecessor-summing counter overcounts. Counting witnesses is easy; counting words is the hard half, and it is hard because the answer itself can be exponential while the input is linear.
The table stays quadratic; the count of distinct longest common subsequences doubles every two characters
Both curves are exact arithmetic, not measurements: the lower one is the cell count, the upper is the count proved above. They cross just past and never meet again.
NextHow do git diff and computational genomics use Hirschberg's linear-space reduction?
Ascending the DP Grid
2 minthe simulation
Hover or click a cell: its predecessor cells light up and the exact recurrence that filled it appears here. Or press play to walk the fill order(56 cells in dependency order).
dp[i][j] = dp[i−1][j−1] + 1 if a[i]=b[j], else max( dp[i−1][j], dp[i][j−1] ).
Longest common subsequence of "ABCBDAB" and "BDCABA".
Hover any cell to light the moves that filled it: from above (skip a character of a), from the left (skip a character of b), or from the diagonal on a match. Press play to fill the 56 cells in dependency order, then Trace solution to read one longest common subsequence out of the grid.
Watch the arrows: a match is a diagonal arrow and a mismatch is one of two skips; press Trace solution and check that the chosen arrows form one staircase, not a scatter of every matching letter.
The top row and left column are all zero, because an empty prefix shares no character with anything. An interior matching cell copies its upper-left neighbour and adds one, tracing a diagonal staircase step.
Off a match, a cell inherits the maximum of its neighbours above and to the left. The bottom-right cell for these words reads 4.
Turn on Trace solution and the trace walks one witness out: four matched cells joined into a staircase, spelling BCAB. Different tie-breaks inside the table produce different witnesses of the same length — that ambiguity is the seed of section 3.4, where the witnesses can outnumber the words.
NextWhat Strong Exponential Time Hypothesis barrier prevents sub-quadratic common subsequence search?
Where Posets Power Modern Toolchains
2 minsystems
diff,patch, and version control. A line diff is a longest common subsequence over lines. Myers 1986 turned the staircase into an walk along its diagonals, where is the edit distance, sodiff,patchandgit diffcost the size of the change rather than the size of the files. The picture a diff tool draws is the staircase of section 3.2.- Sequence alignment. Needleman and Wunsch 1970 scored this recurrence over amino acids, and Smith and Waterman 1981 dropped the requirement to span both strings. Flip a mismatch to a negative score and the same grid aligns locally. Every alignment score in bioinformatics is this table.
- Longest increasing subsequence. When is a rearrangement of , map each character of to its position in to obtain permutation . Then , connecting string alignment directly to the Longest Increasing Subsequence page.
- Plagiarism and duplicate detection. Comparing documents, source files, or product titles is an LCS or an edit distance over tokens, and the same staircase decides which spans match.
Bit-Parallel Speedups and the SETH Barrier
The exact table is not the last word when the strings share few characters. Hunt and Szymanski 1977 listed only the matching cells for time with , which wins when matches are sparse.
Masek and Paterson 1980 used the four-Russians method to reach . Crochemore, Iliopoulos, Pinzon and Reid 2001 packed the recurrence into machine words for bit operations.
Against all of that, the quadratic barrier appears immovable. Abboud, Backurs and Williams 2015 show that an algorithm for LCS would refute the Strong Exponential Time Hypothesis.
This is a conditional lower bound, not an absolute impossibility proof. It explains why the quadratic grid has stood unchallenged since Wagner and Fischer 1974.
Lineage & Attributions
- Wagner and Fischer 1974 — The string-to-string correction problem: the dynamic program, of which this table is the insert/delete case.
- Hirschberg 1975 — A linear space algorithm for computing maximal common subsequences: reconstruction in space by divide and conquer, quadratic time kept, quadratic memory dropped.
- Myers 1986 — An difference algorithm and its variations: the diagonal walk that turns the staircase into the diff tool.
- Needleman and Wunsch 1970 — the alignment recurrence scored over protein sequences, the ancestor of the general grid.
- Smith and Waterman 1981 — local alignment, the same grid without the requirement to span both strings.
- Hunt and Szymanski 1977 — the matching-cell algorithm, .
- Masek and Paterson 1980 — the four-Russians string-edit algorithm.
- Crochemore, Iliopoulos, Pinzon and Reid 2001 — the bit-parallel LCS algorithm, .
- Abboud, Backurs and Williams 2015 — the SETH-conditional lower bound ruling out a truly subquadratic LCS, at the strength of a conditional result.