Myers Diff (Sketched)

Eugene Myers' 1986 algorithm: the basis of git diff. Better than naive LCS for typical diff workloads.

The insight: you can find the shortest edit script by exploring an "edit graph" using BFS bounded by edit distance D.

Total time: O((N + M) * D)
Where D = size of edit script (usually small for similar files)

For typical code edits where most lines are unchanged, D << N. So Myers is much faster than O(N*M) LCS.

Sketch of the algorithm:

1. Build edit graph: nodes are (i, j) pairs; horizontal moves = insert, vertical = delete, diagonal = match.
2. BFS from (0, 0) to (N, M).
3. Each "step" of BFS expands all D-distance frontier points.
4. At each step, "snake" along diagonals (free matches).

Implementation is dense (~50 lines of careful array bookkeeping). Most production diff tools use Myers as the foundation, then layer:

• Patience diff (Bram Cohen): better for code with shifts; finds unique anchor lines first
• Histogram diff: like patience but faster
• Heckel's algorithm: O(N+M) but produces less-optimal diffs

git diff --histogram is the modern recommendation for code.

For this lesson we won't implement Myers — too dense for one problem. We use the LCS-based diff.