Longest common subsequence

In October 2026 a paragraph about Kerckhoffs’s principle in a chapter of this site’s basic course, in its Russian edition, was rewritten: it had 102 words and came to have 89. How many words of the old draft survived into the new one, and in the same order, so that they can be read in a row skipping the rest? 58. That is the longest common subsequence of the two drafts. The scene shows it right in the text, with what was struck out crossed through and what was written in underlined, and under the text the table that found it. Choose another paragraph or switch to letters.

The paragraphs were edited in different ways. The paragraph about the error in Ada Lovelace’s table kept 33 of its 54 words: the edit mostly struck out. The paragraph about forecasting a program’s running time kept only 16 of 51: it was rewritten almost from scratch. This shows in the table too: for an almost unchanged text the orange path runs in a smooth diagonal, for a rewritten one it breaks into long steps where some words are only struck out and others only written in.

Switch to letters. The Kerckhoffs paragraph has 488 common characters out of 662, a larger share than of words, but look at what they read: «ТОглянеперьмся». A common subsequence of letters honestly glues together chance matches, a «т» from «Теперь» with a «т» from anything at all. That is why comparison tools work with larger pieces: with lines, like diff, or with words, like git diff --word-diff. The larger the piece, the fewer chance matches and the closer the answer to what a person did.

The idea

The longest common subsequence of two sequences is the longest sequence that can be obtained from each by striking out elements without changing the order of the rest. For «КОЛОС» and «СОКОЛ» (“ear of grain” and “falcon”) it is «КОЛ»: strike out «ОС» from the first and «СО» from the second. The elements can be anything that can be compared for equality: letters, words, lines of a file, genes.

Look at the last elements of the two sequences. If they are equal, they can be put at the end of the common subsequence, and the same problem remains without them. If they differ, at least one of them is not in the answer: throw it out, and again the same problem remains, only shorter; which of the two to throw out is unknown, so try both. The answers for all pairs of beginnings go into an (m + 1) × (n + 1) table, and the answer itself is read from it by a path back from the bottom right corner.

Formally: T[i][j] is the length of the longest common subsequence of the first i elements of a and the first j elements of b.

Here is the table for «КОЛОС» and «СОКОЛ» as the listing prints it:

      С  О  К  О  Л
   0  0  0  0  0  0
К  0  0  0  1  1  1
О  0  0  1  1  2  2
Л  0  0  1  1  2  3
О  0  0  1  1  2  3
С  0  1  1  1  2  3
LCS(КОЛОС, СОКОЛ) = КОЛ, 3 letters

The numbers rise in terraces: to the right and downwards they do not decrease, and each next terrace is one higher than the previous. One can climb to a new terrace only through a cell where the elements matched: it is the only place in the formula where the “+ 1” appears. In the scene all matches are marked with dots, and those standing at a terrace’s corner lift to the new terrace. These corner matches are what James Hunt and Douglas McIlroy called candidates, and they built the first diff in Unix on them; more on it below.

Why the table is right

The answer is a path from the corner

The table stores only lengths. The words themselves are recovered by a path back from cell (m, n): if the last elements are equal, this is an element of the answer, and the path goes diagonally; if not, to the neighbouring cell, above or to the left, with the larger number. A step up means a word of the old draft was struck out, a step left that a word of the new one was written in. This gives not only the common part but the whole edit: the orange line in the scene.

When the numbers above and to the left are equal, both steps will do, and different rules give different, equally long answers. Our path goes up on a tie. There can be very many longest common subsequences, and this is no trifle: the gluing “common to the first two, then common with the third” stumbles on it in the three-drafts problem below.

Each step of the path except the diagonal ones is one edit, a deletion or an insertion. So the smallest number of deletions and insertions that turn one sequence into the other equals m + n − 2·T[m][n]. This is the edit distance without substitutions, and it is exactly what the Myers diff looks for: the same path over the same grid, only found by waves, without filling the whole table. For the Kerckhoffs paragraph it is 102 + 89 − 2 · 58 = 75 edits: 44 words struck out, 31 written in.

Code

The table, the path back and the edit printed in the manner of git diff --word-diff: the struck out in [-…-], the written in in {+…+}. First «КОЛОС» and «СОКОЛ», then all five paragraphs from the scene and the whole edit of the first of them.

The edit of the Lovelace paragraph reads like an editor’s work: “most likely” became “usually”, “a typo” became “considered a typo”, three sentences in the middle were squeezed into one. The table does not understand this: it only found the longest chain of surviving words and declared everything else struck out or written in.

Hirschberg: the answer in linear memory

For the length of the answer the whole table is not needed: row i is computed only from row i − 1, and two rows are enough. But the path back runs over the whole table, and to recover the answer itself it seems all of it is needed. In 1975 Daniel Hirschberg counted what this costs: two strings of a thousand characters are a million cells, a megabyte of memory, which was not easy then; two strings of ten thousand, and the problem may simply not fit in main memory. And Hirschberg proposed a way to find the answer itself while keeping only a few rows.

Take the middle row of the table. The best path crosses it somewhere. Compute the table from the top down to the middle row: this gives, for each column k, the length of the common part of the upper half of a and the first k elements of b. And likewise from the bottom: the length of the common part of the lower half of a and the rest of b after k. The sum of the two numbers is the length of the best path through the point (middle, k), and where the sum is largest, the best path crosses the middle. Now the problem has split into two, each half as many rows: the top left rectangle and the bottom right one.

The rectangles shrink towards the path: everything further from it is thrown away after the very first split. At each level of recursion the rectangles together take half the area of the previous level: the rows are halved, and the columns are just shared between the two parts. The areas add up to mn + mn/2 + mn/4 + … < 2mn: twice as many cells as in the table, and memory of a few rows.

The AlphaGo paragraph by letters is 508 and 665 characters. The table is 337,820 cells and almost 339 thousand numbers in memory. Hirschberg computes 674,942 cells, exactly twice as many, but keeps at most 1998 numbers in memory, three rows of 666, with a recursion depth of 10. The answer is of the same length, 394 characters. Not necessarily the same one: of the many longest common subsequences Hirschberg picks its own, by the leftmost of the best crossings.

The same technique works wherever the table is a grid of paths: in edit distance, in gene alignment, in the Myers diff, where the middle snake plays its role. This is divide and conquer on top of dynamic programming: the dynamic programming finds where to split, and the splitting saves storing the table.

What it costs

A benchmark on random DNA strings of equal length: the table with the answer, two rows for the length only, and Hirschberg.

All three lines have slope 2: strings twice as long, four times the work. In Python Hirschberg is almost twice as slow as the table, as the cell count promises. In Go it is different: on strings of 4800 letters the table of 23 million numbers runs into memory, and Hirschberg overtakes it twofold, while two rows run almost three times faster than the table: all their data lies in the processor cache.

Substantially faster than quadratic is not possible in general, if the strong exponential time hypothesis is to be believed: in 2015 Amir Abboud, Arturs Backurs and Virginia Vassilevska Williams, and independently Karl Bringmann and Marvin Künnemann, showed that an O(n^{2 − ε}) algorithm for the longest common subsequence would refute this hypothesis.

When matches are few

In a file most lines are unique, and there are far fewer pairs of equal lines in two versions than cells in the table: the table spends almost all its time on cells where nothing happens. The first diff in Unix, described by James Hunt and Douglas McIlroy in a Bell Laboratories report in July 1976, looked for the longest common subsequence of lines and looked only at the “candidates”, the matches at the corners of terraces. Each line of a file usually has few candidates, and binary search finds their place in the current list. According to the authors, on real files time and memory grow roughly as the sum of the file lengths, although in the worst case as the product. A year later Hunt and Thomas Szymanski published this technique as an O((r + n) log n) algorithm, where r is the number of pairs of equal elements.

The limiting case is especially pretty. If each element occurs once in each sequence, write out, for the elements of the first, their places in the second. A common subsequence is a set of elements whose places increase, that is, a longest increasing subsequence, and the staircase finds it in O(n log n) instead of quadratic time. Patience diff in git stands on this, and it is the second problem below: the frequency dictionaries of the two halves of War and Peace.

Three strings and more

For three sequences the table becomes a cube: cell (i, j, k) is the answer for three beginnings, and the formula is the same: if the three last elements are equal, one plus the diagonal cell, otherwise the maximum of three neighbours. For k strings of length n there are n^k cells, and apparently there is no getting away from this: in 1978 David Maier proved that for an arbitrary number of strings the problem is NP-hard, even with a two-letter alphabet. It is tempting to compute the common part of the first two and then the common part of the result and the third, but that is a mistake, and the three-drafts problem catches it on a real paragraph of the course.

Where it works

• Comparing versions. The first diff looked for the longest common subsequence of lines; today’s usually look for the shortest edit script with the Myers algorithm, but it is the same problem. git diff --word-diff shows an edit word by word, in the very brackets [-…-]{+…+} that our listing prints.
• Scoring machine text. ROUGE-L, one of the measures for comparing a machine summary with one written by a person, counts the share of words in their longest common subsequence (Chin-Yew Lin, 2004). Word order is taken into account, and gaps are not penalised.
• Biology. Aligning genes and proteins is the same table with weights for matches, substitutions and gaps: Needleman–Wunsch and Smith–Waterman.
• Not where you expect it. The difflib module of Python’s standard library does not look for the longest common subsequence. Its documentation says plainly that it looks for the longest contiguous common piece, then recursively takes apart what is left and right of it, and does not promise a minimal edit: such edits, according to the authors, often look unnatural to people.

History

The problem grew out of several sciences at once, out of comparing proteins and out of string correction, where in the early 1970s it was solved with the same table as edit distance. The best-known works on it appeared almost simultaneously: Hirschberg defended a dissertation on the longest common subsequence in 1975, the same year Szymanski issued a report on a special case of it, and Hunt and McIlroy cited both when describing diff. In the 1975 paper Hirschberg estimated that for strings of ten thousand characters the method would need a little over three minutes and a hundred kilobytes of memory, where the table would need a hundred million cells.

Problems

The first is about a text edited twice: what survived both edits. The catch is that the common part of three cannot be assembled from the common part of two. In the second the lists are too long for a table, but each word occurs in them once.