Longest Common Subsequence: The Diff Algorithm

Subsequence, not substring

A subsequence keeps the relative order of characters but does not require them to be adjacent — "ACE" is a subsequence of "ABCDE", skipping B and D. The longest common subsequence (LCS) of two strings is the longest sequence that is a subsequence of both. It is a deceptively simple question — "what is the biggest chunk these two things share, allowing gaps?" — that turns out to be exactly the right formalisation of "how similar are these two files, these two DNA strands, these two versions of a document."

The recurrence

Let dp[i][j] be the length of the LCS of the first i characters of A and the first j characters of B. Unlike edit distance, there is no cost for a mismatch — a mismatched pair simply cannot both be included, so the recurrence takes the best of skipping one character from either string:

dp[0][j] = dp[i][0] = 0

dp[i][j] = dp[i-1][j-1] + 1              if A[i] == B[j]
dp[i][j] = max(dp[i-1][j], dp[i][j-1])   if A[i] != B[j]

Filling this (n+1)×(m+1) grid costs O(nm) time and space, same as edit distance — the two problems are close cousins, and LCS length is in fact equal to n + m minus twice the edit distance when only insertions and deletions (no substitutions) are allowed.

Tracing the diagonal matches

Starting from the bottom-right cell, follow the same kind of backward trail used for edit distance: whenever A[i] equals B[j], the cell must have come from a diagonal step and that character belongs to the LCS; otherwise step to whichever of the up/left neighbours matches dp[i][j] and try again. Collecting the characters found on diagonal steps, in reverse order, spells out one valid longest common subsequence — there may be several of equal length, and which one this trace recovers depends on tie-breaking.

The algorithm behind every diff you have read

A line-based diff treats each file as a sequence of lines and computes the LCS of the two sequences. Lines that appear in the LCS are shown as unchanged; everything else is marked added (present in the new file, not in the LCS) or removed (present in the old file, not in the LCS). Git and most modern diff tools do not run the textbook O(nm) DP directly — they use the Myers algorithm, which finds the same shortest edit script by searching over "diagonals" in an implicit edit graph, typically running much faster than O(nm) when the two files are largely similar, which is the common case in version control.

DNA, proteins, and beyond text

LCS treats every match as free and every mismatch as a forced skip, which is a reasonable model for plain text but too blunt for biology, where a substitution and an insertion rarely carry the same evolutionary cost. Bioinformatics uses the same diagonal/up/left DP structure but with a scoring matrix — the Needleman-Wunsch algorithm for a full end-to-end alignment, Smith-Waterman for finding the best matching local region within two longer sequences. Both are, structurally, LCS with weights attached, which is why understanding the plain unweighted version first makes the biological algorithms much easier to follow.

Frequently asked questions

Try it live

Everything above runs in your browser — open Longest Common Subsequence and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.