LCS Algorithm Explained: How Diff Tools Find Changes

Paste two versions of a file into a diff tool and it instantly highlights what moved, what vanished, and what's new. That's not string matching — it's an algorithm solving the longest common subsequence (LCS) problem, then reporting everything outside that subsequence as an edit. Understanding LCS explains why a good diff shows a two-line change instead of rewriting your whole function, and why some diffs look smarter than others.

#TL;DR

• LCS = the longest run of lines shared, in order, between two texts.
• Everything not on the LCS is an insertion or a deletion.
• The textbook LCS solution is O(mn) — too slow for big files.
• Git and most tools use Myers' faster O(ND) diff algorithm.
• Patience and histogram diffs trade speed for more readable output.

#What is the LCS algorithm?

The longest common subsequence problem asks: given two sequences, what is the longest sequence of elements that appears in both, in the same relative order, without needing to be contiguous?

#Subsequence vs substring

These two words trip people up. A substring is a contiguous slice — BCD is a substring of ABCDE. A subsequence only preserves order, gaps allowed — BD and ACE are both subsequences of ABCDE. A diff cares about subsequences because unchanged lines in a file are almost never contiguous; edits are sprinkled between them.

#Why diff uses the longest common subsequence

If you find the longest thing two files share in order, then by definition the leftover elements are the smallest possible set of changes. Keep the shared subsequence fixed as "context," delete the extra elements from the old file, and insert the extra elements from the new file. Maximising what's common is the same as minimising the edit — the two are mathematically equivalent, a point Eugene Myers made central to his 1986 paper.

#A worked example

Compare ABCABBA and CBABAC. One longest common subsequence is BABA (length 4). Lock those four characters in place, and the diff is just the handful of insert/delete steps around them. There can be more than one valid LCS of the same length — CABA is another length-4 answer here — which one a tool picks is why two correct diff tools sometimes disagree on how to show an identical change. Neither is wrong; they simply chose a different optimal path through the same problem.

The line-level case works identically, just with whole lines as the "characters." A diff tool hashes each line, runs LCS over the resulting sequence of hashes, then maps the result back to the original text. That's why swapping two lines can register as a delete-plus-insert rather than a move: LCS has no concept of a line moving, only of a line being present or absent in order.

#How does a diff tool find changes?

The classic answer is dynamic programming: build a table, fill it bottom-up, then walk back through it to recover the actual edits.

#Building the LCS table

For inputs of length m and n, allocate an (m+1) x (n+1) grid. Cell [i][j] holds the LCS length of the first i elements of one input and the first j of the other. The recurrence is short:

// dp[i][j] = LCS length of A[0..i], B[0..j]
if (A[i - 1] === B[j - 1]) {
  dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
  dp[i][j] = Math.max(
    dp[i - 1][j],
    dp[i][j - 1]
  );
}

When two elements match, you extend the diagonal; when they don't, you carry over the better neighbour. The bottom-right cell ends up holding the full LCS length.

#Backtracking to the edit script

The length alone isn't a diff. Starting from the bottom-right corner, walk backwards: a diagonal step means "keep this line," a step up means "delete," a step left means "insert." The path you trace is the edit script — the exact sequence of keeps, deletes, and inserts a diff viewer renders.

#From edit script to insertions and deletions

Once you have that script, the presentation is cosmetic. A unified diff prints - and + lines; a side-by-side view lines the two columns up. Either way, the underlying decisions came straight from backtracking the LCS table. The same edit script drives whether you're diffing prose, Markdown drafts, or two JSON payloads.

#LCS dynamic programming vs Myers diff algorithm

The DP table is correct and easy to teach — but it doesn't scale, which is why production tools reach for something smarter.

#Why O(mn) is too slow for real files

Filling every cell costs O(mn) time and O(mn) memory. For two 10,000-line files that's 100 million cells. Diffs usually involve files that are mostly identical with a few changes, so 99% of that table is wasted work spent confirming lines that obviously match.

#How the Myers algorithm speeds it up

In 1986 Eugene Myers published "An O(ND) Difference Algorithm and Its Variations," where N is the combined input size and D is the size of the edit — the number of insertions plus deletions. When two files are similar, D is tiny, so the algorithm is close to linear in practice. Because most diffs are small edits to large files, this is a massive win over O(mn). Myers is the default in Git for exactly this reason.

#The edit graph and shortest path

Myers reframes the problem as a graph search. Lay the two files on the axes of a grid; a diagonal edge means the characters match (a free move), a horizontal or vertical edge is a delete or insert (costs one). Finding the shortest common subsequence becomes finding the shortest path from top-left to bottom-right. The algorithm does a greedy breadth-first search by edit distance d, extending the furthest-reaching path on each diagonal before spending the next edit — as James Coglan's walkthrough of the paper lays out step by step. Because it stops the moment it reaches the far corner, it never fills the parts of the table that a similar pair of files would waste time on. Myers also describes a linear-space refinement that runs in O(N log N + D²) time by recursively splitting the edit graph at its midpoint, so even huge files don't blow up memory the way the naive O(mn) table would.

#Which diff algorithm does Git use?

Git ships four diff algorithms, and you pick one with --diff-algorithm:

git diff --diff-algorithm=patience
git diff --diff-algorithm=histogram

Per the Git documentation, the choices are myers (default), minimal, patience, and histogram.

#Myers, minimal, patience, histogram

Each makes a different trade between speed and readability:

The Git docs describe minimal and histogram as the improved versions of Myers and patience respectively.

#When Myers produces a confusing diff

Myers minimises edits, but "fewest edits" isn't always "most readable." Add a function above an existing one and Myers may pair your new closing brace with the old function's brace, producing a diff that straddles both blocks. It's technically minimal and genuinely confusing — a classic complaint with code that repeats lines like } or blank separators.

#Patience and histogram explained

Patience diff (named after the card game) first matches only lines that appear exactly once in both files, uses those as reliable anchors, then recurses into the gaps. This keeps unique markers — function signatures, imports — aligned, so the diff reads the way a human would group the change. Histogram extends patience to handle low-frequency repeated lines and runs faster, which is why many teams set it as their default. A 2019 empirical study on arXiv found the algorithms can produce meaningfully different diffs on the same commits, so the choice isn't purely cosmetic.

Some things to keep in mind when the algorithm choice matters:

• Reordered or moved code benefits most from patience or histogram.
• Minimal is worth the cost only for small, high-stakes diffs.
• Whitespace settings change the input before LCS ever runs — see the whitespace note below.
• All four keep the LCS core; they differ mainly in anchor selection.

#References

• An O(ND) Difference Algorithm and Its Variations (Eugene W. Myers, 1986) — the primary paper; used for the O(ND) complexity, edit-graph model, and the LCS/edit-script equivalence.
• Git — diff-algorithm option documentation — official reference for the myers, minimal, patience, and histogram options and their relationships.
• The Myers diff algorithm: part 1 — James Coglan — author-attributed walkthrough; used for the greedy shortest-path search over the edit graph.
• How Different Are Different diff Algorithms in Git? (arXiv) — empirical study; used to support that algorithm choice changes real diff output.

#Related on iKit

• Run any two texts through a browser diff in seconds — the practical companion to this theory: paste, compare, and see the edit script rendered live, no upload.
• Side-by-side vs unified diff, and why the layout differs — both views are the same LCS edit script presented two ways; this explains when to reach for each.
• What "ignore whitespace" really does before the diff runs — whitespace options preprocess the input before LCS sees it, which is why they can quietly hide a real change.