Card 02/ 09
Fill a Longest Common Subsequence Table
A match extends the diagonal; otherwise the entry keeps the better of the cell above and the cell to the left.
Filling a longest common subsequence table means visiting each entry row by row and, when the two last characters match, adding 1 to the entry on the diagonal, and otherwise copying the larger of the entry above and the entry to the left. This walkthrough fills the table for MONEY and LEMON, reads the length from the last cell, walks back to recover the subsequence itself, and then separates a subsequence from a substring.
The rows are the prefixes of MONEY and the columns the prefixes of LEMON, each starting with the empty prefix, whose row and column are all 0. Cells marked [ ] are those where the two characters match.
Before the table: how long is the longest common subsequence of MONEY and LEMON, and what is it?
3, and the subsequence is MON, which appears in order in both words. The table below reaches it entry by entry.
Filling the table for MONEY (rows) and LEMON (columns)
Row M
M differs from L and E, so those entries take the larger of above and left, both 0. M matches the M of LEMON, so that entry is the diagonal, 0, plus 1. The two entries after it copy the 1 from their left.
| Prefix | Empty | L | E | M | O | N |
|---|---|---|---|---|---|---|
| Empty | 0 | 0 | 0 | 0 | 0 | 0 |
| M | 0 | 0 | 0 | [1] | 1 | 1 |
Row O
O matches only the O of LEMON. Its diagonal is the M entry of row M, which holds 1, so the match makes 2: MO is common to both. The entries before it copy the 1 from above, and N copies the 2 from its left.
| Prefix | Empty | L | E | M | O | N |
|---|---|---|---|---|---|---|
| Empty | 0 | 0 | 0 | 0 | 0 | 0 |
| M | 0 | 0 | 0 | 1 | 1 | 1 |
| O | 0 | 0 | 0 | 1 | [2] | 2 |
Row N
N matches the last N of LEMON, and its diagonal holds 2, so the entry becomes 3: MON.
| Prefix | Empty | L | E | M | O | N |
|---|---|---|---|---|---|---|
| Empty | 0 | 0 | 0 | 0 | 0 | 0 |
| M | 0 | 0 | 0 | 1 | 1 | 1 |
| O | 0 | 0 | 0 | 1 | 2 | 2 |
| N | 0 | 0 | 0 | 1 | 2 | [3] |
Rows E and Y
E matches the E of LEMON, but its diagonal is 0, so the match makes only 1: E comes after MON in MONEY and before it in LEMON, so it cannot join them. Y matches nothing. Every later entry in both rows copies a larger value from above, so the last cell stays 3.
| Prefix | Empty | L | E | M | O | N |
|---|---|---|---|---|---|---|
| Empty | 0 | 0 | 0 | 0 | 0 | 0 |
| M | 0 | 0 | 0 | 1 | 1 | 1 |
| O | 0 | 0 | 0 | 1 | 2 | 2 |
| N | 0 | 0 | 0 | 1 | 2 | 3 |
| E | 0 | 0 | [1] | 1 | 2 | 3 |
| Y | 0 | 0 | 1 | 1 | 2 | 3 |
The length is the last cell, 3, which a run confirmed. To recover the subsequence, start at that cell and walk back. Where the two characters match, the character belongs to the subsequence: record it and step diagonally. Otherwise step to whichever of above and left holds the larger value, preferring above on a tie. From Y and N the walk goes up twice, to row N, then diagonally at N, at O and at M, which reads MON backwards. The run printed the same path.
A subsequence may have gaps and a substring may not, and the two answers can differ. MONEY and LEMON share MON as a substring too, so both answers are 3. TRAIN and TRIAL share the subsequences TRA and TRI, of length 3, but the longest run of adjacent letters they share is TR, of length 2; a run printed both lengths. A longest common substring needs a different recurrence, which resets an entry to 0 on a mismatch instead of copying a neighbour.
← → move through sections and cards