How Text Diffing Works: The Longest Common Subsequence & Myers Algorithm

Every software engineer interacts with text diffing constantly: running git diff, reviewing GitHub pull requests, resolving merge conflicts, and inspecting database schema changes.

When two versions of a document or source file are compared, how does a computer determine the minimal set of line additions, deletions, and modifications needed to transform Version A into Version B?

---

The Core Problem: The Edit Distance

Comparing two texts is not as simple as checking if line 1 matches line 1. If you insert a single new line at the very top of a 1,000-line file:

• A naive line-by-line comparison would report that all 1,000 lines changed!
• An intelligent diff engine recognizes that a single line was added, and that lines 2 through 1,001 are identical to the original file.

Finding this optimal alignment is an instance of the Shortest Edit Script (SES) problem, which is mathematically dual to finding the Longest Common Subsequence (LCS).

---

1. The Longest Common Subsequence (LCS)

A subsequence is a sequence that appears in the same relative order, but not necessarily contiguously.

Consider two strings:

• String A: A B C D G H
• String B: A E D F H R

The Longest Common Subsequence between them is A D H (length 3).

• Everything in String A that is not in the LCS was deleted (- B, - C, - G).
• Everything in String B that is not in the LCS was added (+ E, + F, + R).

---

2. Eugene Myers' $O(ND)$ Algorithm (The Git Standard)

In 1986, computer scientist Eugene W. Myers published a breakthrough paper: "An O(ND) Difference Algorithm and Its Variations".

Myers framed the diff problem as finding the shortest path on an edit graph:

• Moving right represents a deletion from text A.
• Moving down represents an insertion into text B.
• Moving diagonally represents matching identical lines (cost = 0).

Because typical code edits involve only a few changed lines ($D$) among thousands of total lines ($N$), Myers' algorithm scales with the number of differences rather than file length, making it extraordinarily fast and memory-efficient.

---

3. Unified Diff Format

The standard text representation for diffs popularized by Unix and Git is the Unified Diff Format:

@@ -1,4 +1,5 @@
 import React from 'react'
-import { LegacyButton } from './legacy'
+import { Button } from '@/components/ui'
+import { Tooltip } from '@/components/ui'
 export default App

• Lines starting with - (red) were deleted.
• Lines starting with + (green) were added.
• Unprefixed lines provide contextual anchoring.

---

Compare Two Texts or Code Files Instantly

Need to quickly inspect the differences between two contracts, markdown articles, or configuration files? Use our free Diff Checker. It uses local browser execution to compute additions and deletions without transmitting your sensitive text to any remote server.