Edit Distance answers "what's the fewest edits,
allowing substitution?" by filling every cell of an (m+1)×(n+1) table. Real
diff tools ask a narrower question, and answer it without substitution at all: only
insert and delete are allowed, and the two sequences being compared (source lines, not
characters, for git diff) are usually mostly the same — a handful of real
edits buried in a lot of unchanged material. Myers' algorithm (1986) exploits
that directly: instead of filling a table sized by the input, it searches outward by number of
edits, D = 0, 1, 2, …, and stops the instant a D-edit path reaches the
end — so the cost scales with how different the inputs actually are, not with their
raw size.
The classic pair from Myers' own 1986 paper: A = "ABCABBA",
B = "CBABAC". Picture an edit graph: a grid of points
(x, y) for every prefix-length pair of A and B, with a free
diagonal move wherever A[x] = B[y] (a "snake") and a one-edit-cost move right
(delete A[x]) or down (insert B[y]) everywhere else. Press
Step or Run — the demo tries D = 0, then
D = 1, and so on, and for each D sweeps every relevant
diagonal k = x − y, extending the furthest point already reached one
step further and then sliding it along any matching run it lands on. The moment a point reaches
(7, 6) — the bottom-right corner — that D is the answer, and the demo
backtracks to recover the actual edit script.
Switch mode to buggy (skip the snake) to run the broken
variant Pitfalls describes, live: the search still expands by D and still visits the
same diagonals, but every free diagonal move through a matching run is skipped. Watch the grid —
the diagonal runs through matching characters (shown as connected dots) never appear, and the
search needs every one of D = 13 steps (one per character of both strings) instead of
the true 5, because it never notices that eight of the thirteen positions
already agree.
Every point in the edit graph lies on exactly one diagonal k = x − y, and a key
fact makes the search cheap: a D-edit path can only ever reach diagonals
k ∈ {−D, −D+2, …, D−2, D} (each edit moves one diagonal left or right, so
D edits land on a diagonal whose parity matches D's), and on any one
diagonal, only the furthest-reaching point any D-edit path can reach
matters — a shorter reach on the same diagonal can never do anything a longer reach couldn't
already do, since both face the same remaining grid. So the algorithm keeps exactly one number per
diagonal, V[k] = the furthest x reached on diagonal k so
far, and updates it as D grows: reaching diagonal k with D
edits means arriving from diagonal k − 1 (one delete, moving right) or diagonal
k + 1 (one insert, moving down) using only D − 1 edits — take whichever
of those two predecessors reached further, since it can only help.
After that one edit move, the point slides diagonally through every immediately-following
matching character for free — that's the "snake." Snakes are what make the algorithm cheap on
realistic inputs: each one shortcuts past however many characters happen to already agree, at zero
edit cost, so D only counts genuine differences. In the worst case (no two characters
ever match) D = N + M and the algorithm degrades to checking every diagonal at every
step — no better than the full table — but that worst case is rare for real diffs, which is
exactly why diff and git diff use this algorithm instead of the plain
O(N·M) table Longest
Common Subsequence fills.
Returns the shortest edit distance D and a trace of every intermediate
V array, which the backtrack step below walks in reverse to recover the actual
script:
function shortestEdit(a, b) {
const N = a.length, M = b.length;
const MAX = N + M;
const offset = MAX; // V is indexed -MAX..MAX; offset shifts it into a plain array
const V = new Array(2 * MAX + 1).fill(0);
const trace = [];
for (let D = 0; D <= MAX; D++) {
trace.push(V.slice());
for (let k = -D; k <= D; k += 2) {
let x;
if (k === -D || (k !== D && V[offset + k - 1] < V[offset + k + 1])) {
x = V[offset + k + 1]; // came from k+1: an insert (down)
} else {
x = V[offset + k - 1] + 1; // came from k-1: a delete (right)
}
let y = x - k;
while (x < N && y < M && a[x] === b[y]) { x++; y++; } // snake
V[offset + k] = x;
if (x >= N && y >= M) return { D, trace };
}
}
}
function backtrack(a, b, trace) {
const N = a.length, M = b.length, offset = N + M;
let x = N, y = M;
const ops = [];
for (let D = trace.length - 1; D >= 0; D--) {
const V = trace[D];
const k = x - y;
const prevK = (k === -D || (k !== D && V[offset + k - 1] < V[offset + k + 1])) ? k + 1 : k - 1;
const prevX = V[offset + prevK], prevY = prevX - prevK;
while (x > prevX && y > prevY) { ops.push({ op: 'match', ax: --x, by: --y }); }
if (D > 0) {
if (x === prevX) ops.push({ op: 'ins', by: prevY });
else ops.push({ op: 'del', ax: prevX });
}
x = prevX; y = prevY;
}
return ops.reverse();
}Skip the snake and the algorithm doesn't get the wrong answer — it gets the
slowest possible right one. Checked against the shipped page's own
buggy (skip the snake) mode on "ABCABBA"/"CBABAC": without the
diagonal slide through matching runs, every point only ever advances by exactly one row or column
per edit, so the search never discovers any of the eight positions where the two strings actually
agree. It still terminates and still returns a technically-valid edit script — just the worst one,
D = 13 (delete all seven characters of A, insert all six of
B) instead of the true minimum, 5. Unlike
Banded Edit Distance's sentinel bug,
this failure isn't a wrong number masquerading as a right one — it's a correct-shaped answer that's
needlessly, silently, worse.
The diagonal step has to be 2, not 1 — and getting it wrong produces an answer smaller
than what's mathematically possible. A D-edit path can only land on
diagonals whose parity matches D's (each edit shifts the diagonal by exactly one, so
D shifts always land D steps, not D − 1 or D + 1,
from diagonal 0). Loop k from −D to D in steps of 1 instead
of 2, and half of every iteration reads V[k − 1] and V[k + 1] at slots
that belong to the wrong diagonal's leftover value from an earlier, unrelated
D — checked in a scratch variant on the same pair: it terminates at
D = 3, not 5. That number isn't just wrong, it's impossible on its face — the
identity D = N + M − 2·L (where L is the two strings' true longest
common subsequence length, independently confirmed at 4 by the DP table) puts a hard floor of 5
under any genuine answer for this pair. A caller that only checks "did it return a number" instead
of "is this number even reachable" would never notice.
V has to persist across the whole outer loop — reallocating it fresh for
every D doesn't corrupt the answer, it erases the algorithm's only memory of
progress. The entire point of carrying V forward is that diagonal
k's furthest reach at D edits is built directly from where it (or its
neighbor) already stood at D − 1; start every D from an all-zero array
instead, and the search re-derives nothing from prior work, re-walking from the origin every
round. Checked in a scratch variant on the same pair: it never terminates within the
MAX = N + M bound at all — a different failure shape from either bug above, since it
neither returns a plausible-looking wrong number nor a needlessly large right one, it just never
returns.
Time: O((N + M)·D), where D is the true shortest
edit distance — the outer loop runs D + 1 times and each pass visits at most
D + 1 diagonals, each in amortized constant time plus its snake (snakes across one
run of the outer loop cover at most N + M total steps). When the inputs are mostly
identical, D is small and this beats
Edit Distance's O(m·n) table
by a wide margin; in the worst case, D = N + M and the two become comparable.
Space: O((N + M)·D) for the full trace needed to reconstruct the
script (one V snapshot per D), or O(N + M) for the distance
alone.
Unlike Banded Edit Distance, which needs a
budget k chosen in advance and reports "impossible" if it guessed too small, this
algorithm never needs to guess — it discovers the true D by construction, since it
only stops once a path genuinely reaches the far corner. That's the shape every real
line-oriented diff and git diff actually uses: no edit-cost budget is
ever specified up front, because none is needed. For the DP-table view of the same
insert/delete-only problem, and where the D = N + M − 2·L identity used above in
Pitfalls comes from, see
Longest Common Subsequence. A sixth
entry, Jaro-Winkler Similarity, drops the edit-graph
idea entirely — no diagonals, no minimum edit count, just a bounded matching window and a
transposition tally turned into a similarity score, better suited to short strings like names
than to the line-oriented text this algorithm targets. For a side-by-side comparison across all eleven
approximate-match entries, see Choosing an
Approximate String Matcher.