Longest Common Subsequence Calculator

Understanding the longest common subsequence calculator — concept and principle

A subsequence keeps characters in their original order but may skip some; "ACE" is a subsequence of "ABCDE". The longest common subsequence (LCS) of two strings is the longest sequence that appears, in order, in both. It underlies diff tools, version control merges and DNA alignment. This calculator returns the LCS length and one LCS.

How it is calculated

Let L[i][j] be the LCS length of the first i characters of A and the first j characters of B.

• L[i][0] = L[0][j] = 0.
• If A's i-th character equals B's j-th: L[i][j] = L[i−1][j−1] + 1.
• Otherwise: L[i][j] = max(L[i−1][j], L[i][j−1]).

The answer is L[m][n]. To recover one LCS, the calculator walks back from the bottom-right cell, taking a character on each match and otherwise moving toward the larger neighbor (up when tied). The table takes O(mn) time and memory, so inputs whose product of lengths exceeds 4,000,000 are refused.

The principle

Look at the last characters. If they are equal, an optimal LCS can always end with that shared character, so the problem shrinks to both shorter prefixes. If they differ, at least one of them is not in the LCS, so the answer is the better of dropping A's last character or dropping B's. Every subproblem is a pair of prefixes, and there are only (m + 1)(n + 1) of them, which is why dynamic programming solves it efficiently.

Worked example

1. Inputs: A = "ABCBDAB" (7), B = "BDCABA" (6).
2. Filling the 8 × 7 table gives L[7][6] = 4.
3. Tracing back yields the subsequence BCBA: B, C, B, A appear in this order in both strings (A: positions 2, 3, 4, 6; B: positions 1, 3, 5, 6).
4. Other LCSs of length 4 exist, such as BDAB and BCAB; the calculator shows one.

How to read the result

LCS length ÷ the longer length gives a rough overlap ratio (here 4 ÷ 7 ≈ 57%). The LCS also links to edit distance: if only insertions and deletions are allowed, the distance is m + n − 2 · LCS, which is 7 + 6 − 8 = 5 here. Diff tools use exactly this view: lines not in the LCS are shown as deleted or added.

Common mistakes

• Confusing subsequence with substring; a substring must be contiguous, so the longest common substring is a different problem.
• Expecting a unique answer; several LCSs of the same length are common.
• Forgetting that case and spaces count as characters.

Frequently asked questions

What is the time complexity of LCS?

O(mn) with the standard table. For two strings of 10,000 characters that is 100 million cells.

Can I find all LCSs?

Yes, by branching on ties during the trace-back, but the number of distinct LCSs can grow very quickly.

How is LCS used in diff?

Treating each line as a symbol, the common lines are kept and every other line is reported as removed or added.

Sources: T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, MIT Press (longest common subsequence) · D. S. Hirschberg, "A linear space algorithm for computing maximal common subsequences", Communications of the ACM 18(6), 1975 · E. W. Myers, "An O(ND) difference algorithm and its variations", Algorithmica 1, 1986