How Diff Algorithms Work
When you compare two files, the tool has to decide which lines are the same, which are new and which disappeared. That sounds obvious to a human, but a computer needs a precise rule. The rule almost every diff tool uses is beautifully simple to state and surprisingly deep to implement: find the longest sequence of lines the two files share, and describe everything else as an insertion or a deletion.
The longest common subsequence
The heart of a diff is the Longest Common Subsequence, or LCS. A subsequence keeps the original order but is allowed to skip items, so the LCS of the two files is the largest set of lines that appear, in the same order, in both. Anything in the old file that is not part of the LCS must have been deleted; anything in the new file that is not part of it must have been added. That single insight turns a fuzzy comparison into a concrete calculation.
A textbook LCS uses dynamic programming: a table where each cell reuses the answers to smaller sub-problems. It is correct and easy to understand, but it needs memory proportional to the two lengths multiplied together, which is too much for large files. That cost is exactly why real tools reach for something smarter.
The Myers algorithm
In 1986 Eugene Myers published the algorithm that most modern tools, including Git, still use. It reframes the problem as finding the shortest path through an edit graph — a grid where moving diagonally means a line matched, moving right means a deletion and moving down means an insertion. The fewer non-diagonal moves the path takes, the smaller the diff. Myers finds that shortest path in time proportional to the file size times the number of differences, so when two files are nearly identical it is extremely fast.
This focus on the number of differences is the key to performance. Most edits change a handful of lines in a large file, and Myers does work in proportion to that handful, not to the whole document. DiffScope builds on the same family of algorithms, which is why it stays responsive even on long files.
From lines to words
Line-level diffing is the right first pass, but it is coarse: change one character and the whole line is marked removed and re-added. To fix that, a diff tool runs the same algorithm a second time at a finer grain. When it sees a removed line immediately followed by an added line, it treats them as a modified pair and diffs them word by word, so only the parts that actually changed light up.
The result is the layered highlighting you see in a good review tool: red and green for whole lines that appeared or vanished, and a sharper accent inside a modified line for the exact words that differ. Paste two versions into DiffScope and you can watch both layers at once.
The takeaway
A diff finds the longest run of shared lines and calls the rest insertions or deletions. The Myers algorithm makes that fast by working in proportion to the number of changes — and a second word-level pass shows exactly what moved inside each edited line.
Open the tool and try it now
More guides
Line Diff vs Word Diff: When to Use Each
The same change can be shown as whole swapped lines or as a few highlighted words. Here's why both granularities exist and when each one is clearer.
Reading a Git Diff Without the Guesswork
Those @@ headers and +/- lines look cryptic until you know the pattern. Here's how to read a unified diff line by line and never lose your place.
Comparing Config Files Safely
Config drift causes real outages. Here's how to diff configuration files so you catch the meaningful change without leaking secrets or drowning in noise.