Longest common subsequence (LCS)

When you compare two versions of a file, the lines that did not change are a common subsequence of both. Finding the longest one tells you exactly what was added and what was removed. The same idea lines up DNA strands and suggests spelling corrections, and it is solved by one of the most elegant tables in computer science.

A table with one word along the top and another down the side, numbers in its cells, and a path of orange cells climbing from the bottom right corner
A table with one word along the top and another down the side, numbers in its cells, and a path of orange cells climbing from the bottom right corner

The problem

A subsequence of a word keeps some of its letters in their original order: ACE is a subsequence of ABCDE, but EA is not. A common subsequence of two words is a subsequence of both, and the problem is to find the longest one. A word of length n has 2ⁿ subsequences, so trying them all is hopeless beyond a few letters.

The table

Let len[i][j] be the length of the longest common subsequence of the first i letters of one word and the first j letters of the other. An empty word shares nothing, so the first row and column are 0. If letter i equals letter j, len[i][j] = len[i − 1][j − 1] + 1: the match extends whatever came before it. If not, len[i][j] is the larger of len[i − 1][j] and len[i][j − 1]: drop one of the two letters and keep the better result.

An example

Compare ABCBDAB with BDCABA. The first letter of the second word, B, matches the B in row 2; the C in the third column matches row 3, and so on, each match adding one to the cell up and to the left. The bottom right cell ends at 4. Reading back from there gives BCBA, but BCAB and BDAB are just as long: a longest common subsequence need not be unique.

Reading the answer back

Start at the bottom right cell. If the letters of its row and column match, that letter belongs to the answer: note it and step diagonally up and to the left. Otherwise step to the neighbour, above or to the left, with the larger value, because that is where the cell got its value from. Stop at the first row or column. The noted letters, reversed, are the subsequence.

History and uses

The table method was found independently by several people around 1970, among them Robert Wagner and Michael Fischer, whose 1974 paper solved the closely related edit distance. In 1975 Dan Hirschberg showed how to find the subsequence with far less memory, and in 1976 James Hunt and Douglas McIlroy built the Unix diff program on longest common subsequences of lines. Biologists use the same idea, with scores, to align DNA and protein sequences.

Douglas McIlroy, photographed by Peter Adams for Faces of Open Source. In 1976 he and James Hunt built the Unix diff program on longest common subsequences of lines.
Douglas McIlroy, photographed by Peter Adams for Faces of Open Source. In 1976 he and James Hunt built the Unix diff program on longest common subsequences of lines.

Explore it

Open the app and press Step. The two letters being compared light up in the headings; a match reads the blue cell up and to the left, a mismatch reads the two blue cells above and to the left. When the table is full, the orange path climbs back from the corner and the letters of the answer appear under the table.

Frequently asked questions

How much time and memory does the LCS algorithm need?

O(m·n) time for words of lengths m and n. The full table also needs O(m·n) memory to read the answer back; Dan Hirschberg showed in 1975 how to find the subsequence itself with only O(min(m, n)) memory.

How does diff use the longest common subsequence?

It treats each line of a file as one symbol and finds a longest common subsequence of the two files' lines. Lines in that subsequence are unchanged; the other lines of the old file were deleted, and the other lines of the new file were added.

What about three or more words?

The table gets one dimension per word, so three words of length n need n³ cells. For an arbitrary number of words the problem is NP-hard.

How is LCS related to edit distance?

If only inserts and deletes are allowed, the edit distance of two words is their total length minus twice the length of their longest common subsequence. Allowing replacements as well gives the Levenshtein distance, computed by a very similar table.

Ready to try it?

Open PictorX in your browser — no install, no credit card required to start.

Try the longest common subsequence