- Being filled
- Read from
- Answer
Longest common subsequence (LCS)
Which letters do two words have in common, in the same order? The longest common subsequence answers that, and diff tools, spell checkers and DNA comparisons build on it. Type two words and watch a table of their letters fill up, then trace the answer back from the corner. Press Play to watch the table fill, or Step and Back to go one step at a time. Drag the step slider to jump anywhere. Type two words: the first runs down the side of the table, the second along the top. Each cell holds the length of the longest common subsequence of the letters up to its row and column. At the end the letters are read back from the bottom right cell. New example picks another pair of words. With the board selected, the arrow keys step, the space bar plays and pauses, and Home and End jump to the start and the end.
How it works
- Type two words: the first runs down the side of the table, the second along the top.
- Press Play, or use Step and Back to move one step at a time. Drag the step slider to jump anywhere.
- Watch each cell compare its two letters, then follow the orange path back from the corner to read the answer.
How the table works
A cell holds the length of the longest common subsequence of the first word's letters up to its row and the second word's letters up to its column. The row and the column marked – stand for an empty word, so they are 0. If the two letters of a cell are equal, the cell is one more than the cell up and to the left. If they differ, one of the two letters is not part of the answer, so the cell takes the larger of the cell above and the cell to the left.
Reading back the letters
The bottom right cell is the length of the answer. To find the letters, start there: where the two letters match, that letter is in the subsequence, and you move up and to the left; otherwise you move to the larger of the cell above and the cell to the left. The letters collected on the way, read in reverse, are a longest common subsequence. There can be others of the same length; the read-back finds one of them.
Frequently asked questions
What is the difference between a subsequence and a substring?
A substring is a run of letters next to each other, like ACE in RACER. A subsequence keeps the order but may skip letters, so ACE is also a subsequence of ABCDE. The longest common substring is a different problem with a similar table.
How fast is the LCS algorithm?
For words of lengths m and n the table has m·n cells, each filled in one step, so the work is O(m·n). For two texts of 10,000 lines that is 100 million cells, which is why diff tools use cleverer methods built on the same idea.
Is the longest common subsequence unique?
No. ABCBDAB and BDCABA have three different common subsequences of length 4: BCBA, BCAB and BDAB. The table gives the length; the read-back picks one of them.
Does the LCS tell how similar two words are?
In part. Two words of lengths m and n with a longest common subsequence of length k can be turned into each other by deleting m − k letters and inserting n − k. The edit distance, which also allows replacing a letter, is often a better measure.
Is anything sent anywhere?
No. Everything is worked out in your browser, and your last settings stay in this browser's local storage.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Go to Editor