How Diff Algorithms Work: Longest Common Subsequence Explained

Every time you open a pull request or paste two texts into a diff checker, an algorithm decides which lines to call added, which removed, and which unchanged. It feels like magic, but the core idea fits in one sentence: find the longest sequence of lines that both files share in the same order — everything else is a change. This article builds that intuition with a small worked example, explains why real tools use the Myers algorithm, and answers the classic question of why moved code shows up as delete-plus-add.

The Core Idea: Longest Common Subsequence

A subsequence keeps items in order but does not require them to be adjacent. In the word DEVELOPER, "DVLP" is a subsequence; "LEVED" is not, because the order is broken. The longest common subsequence (LCS) of two files is the longest list of lines that appears in both, in the same order.

Why does that solve diffing? Because the LCS is exactly the set of lines the diff can mark as unchanged. Once you know it, the rest falls out mechanically:

• Lines in the old file but not in the LCS are removals.
• Lines in the new file but not in the LCS are additions.
• The longer the LCS, the fewer changes reported — so finding the longest one gives the smallest diff.

A Worked Example with the LCS Matrix

The textbook way to compute an LCS is a dynamic-programming grid. Compare old file lines A B C B with new file lines B C A B. Each cell holds the LCS length of the prefixes ending at that row and column: if the two lines match, take the diagonal neighbour plus one; otherwise take the larger of the cell above and the cell to the left.

            NEW:   B   C   A   B
             +---+---+---+---+---+
             | 0 | 0 | 0 | 0 | 0 |
      OLD: A + 0 | 0 | 0 | 1 | 1 |
           B + 0 | 1 | 1 | 1 | 2 |
           C + 0 | 1 | 2 | 2 | 2 |
           B + 0 | 1 | 2 | 2 | 3 |
             +---+---+---+---+---+

Bottom-right cell = 3, so the LCS has length 3: B C B

Tracing back through the matrix recovers the LCS itself — B C B — and with it the diff:

- A        (in old, not in LCS: removed)
  B        (in LCS: unchanged)
  C        (in LCS: unchanged)
+ A        (in new, not in LCS: added)
  B        (in LCS: unchanged)

Notice something interesting: the line A did not really disappear — it moved after C. But the algorithm has no concept of movement, only of order-preserving matches, so it reports a removal and an addition. Hold that thought.

Why Diffs Are Minimal-ish, Not Perfect

LCS guarantees the fewest changed lines, but several different diffs can be equally minimal, and the algorithm has no taste for which reads better. The classic offender is repetitive lines — braces, blank lines, END statements. The algorithm may match a closing brace from one function with a closing brace from a completely different function, producing a technically minimal but confusing diff that appears to splice two functions together.

• Git offers alternative heuristics: git diff --patience and --histogram anchor matching on rare, distinctive lines first, which usually yields more human-readable output.
• Minimal is a property of the count, not the pairing — two tools can both be "correct" and still show different diffs.

The Myers Algorithm, Briefly

The full LCS matrix needs N×M cells — for two 10,000-line files, that is 100 million comparisons, mostly wasted, because real file pairs are nearly identical. Eugene Myers' 1986 algorithm exploits this: it explores "how far can I get through both files with 0 differences? with 1? with 2?" expanding outward until the ends of both files are reached.

• Its cost is O((N+M)·D), where D is the number of differences — tiny when files are similar, which is the overwhelmingly common case.
• It greedily follows "diagonals" (runs of matching lines) as far as possible before spending an edit.
• It is the default algorithm in git and the basis of most diff libraries, including the ones running inside browser-based tools like our Diff Checker.

Why Moved Blocks Appear as Delete + Add

Now the earlier observation becomes a general rule. A subsequence must preserve order, so when a block of code moves from the top of a file to the bottom, the algorithm cannot count it in the LCS twice or out of order. It must choose: match the block in its old position or its new one. Either way, the other occurrence becomes a removal plus an addition.

• This is a limitation of the model, not a bug in your tool.
• Git can post-process the result: git diff --color-moved scans the delete/add pairs for identical blocks and colours them as moves.
• Reviewers should stay alert: a "moved" block in a PR may also contain a sneaky one-line edit hiding inside the move.

Performance Notes

• Lines, not characters — diffing line-by-line first shrinks the problem enormously; character-level comparison is applied only within changed line pairs.
• Hashing — tools compare line hashes rather than full strings, making each comparison O(1).
• Trimming common ends — identical prefixes and suffixes are stripped before the algorithm runs, since most edits touch the middle of a file.
• Bail-out heuristics — on pathological inputs (huge files with massive differences), git switches to faster approximate modes rather than computing a perfect minimal diff.

These optimisations are why a diff of two large files feels instant — including client-side, in your browser. To see the output side of the story, read unified vs split view.

Frequently Asked Questions