How Text Diff Algorithms Actually Work

Every time you run git diff, every time Google Docs shows revisions, every time a merge tool highlights conflicts — underneath, the same family of algorithms is at work. They take two pieces of text and figure out the smallest set of changes that turns one into the other.

The most fundamental of these algorithms is the Longest Common Subsequence (LCS). It's been around since the 1970s, and despite decades of optimization, it remains the backbone of most diff tools. Understanding how it works demystifies one of the most common operations in software development.

What problem diff solves

Given two strings — say, an original draft and a revised draft — the diff algorithm finds the minimal set of additions and deletions that transforms one into the other. The output is typically displayed with + and - markers showing what was added and removed.

The naive approach would be to find every possible way to transform one string into the other and pick the smallest. That's exponential in time — completely impractical for anything beyond a few dozen characters.

The clever insight is that the longest common subsequence between the two strings is the part that doesn't change. Everything else is either added or deleted.

Subsequence vs. substring

A substring is a contiguous slice of a string — bcd is a substring of abcde. A subsequence doesn't have to be contiguous — ace is a subsequence of abcde, even though there are gaps.

For diff, we want the longest subsequence (not substring) that appears in both strings. This is more flexible: the unchanged parts don't have to be adjacent.

For example, the strings ABCBDAB and BDCAB have a longest common subsequence of BCAB (length 4) — even though those characters aren't adjacent in either string.

The dynamic programming approach

The classic LCS algorithm uses dynamic programming. We build a 2D table where table[i][j] contains the length of the LCS of the first i characters of string A and the first j characters of string B.

for i in 0..=len(A):
    for j in 0..=len(B):
        if i == 0 or j == 0:
            table[i][j] = 0
        elif A[i-1] == B[j-1]:
            table[i][j] = table[i-1][j-1] + 1
        else:
            table[i][j] = max(table[i-1][j], table[i][j-1])

Once the table is filled, the LCS length is at table[len(A)][len(B)]. To reconstruct the actual subsequence, you trace back from the bottom-right corner.

The time and space complexity is O(m × n) where m and n are the lengths of the two strings. For two strings of 1000 characters each, that's a million cells — manageable on modern hardware, but slow for very large inputs.

Producing the diff

Once you have the LCS, producing the diff is straightforward:

Walk through both strings in parallel.
When characters match (they're part of the LCS), emit them as unchanged.
When characters don't match, emit the A character as deleted and the B character as added.

The result is a sequence of "hunks" — contiguous regions of additions, deletions, or unchanged lines. Tools like diff typically group these into larger hunks for display, with context lines around each change.

Line-based vs. character-based diff

Most diff tools operate on lines, not characters. Two reasons:

Performance. A document with 10,000 lines has 10,000 elements in each sequence, not 500,000 characters.
Meaningful output. Showing that line 5 of a JSON file changed is useful; showing that character 247 changed is noise.

For most use cases — code reviews, document revisions, configuration changes — line-based diff is the right granularity. Character-based diff is useful for very short strings (single-line values, names) where the line is small enough that character-level changes are meaningful.

Word-level diff

Some tools offer word-level diff, which sits between line and character granularity. This is useful for natural language text where a sentence might be rewritten without changing much.

Word-level diff treats each word as an atomic unit. The algorithm is the same as line-based diff; only the unit changes. The result shows which words were added, removed, or moved — useful for editing prose.

Myers' algorithm

The classic LCS algorithm is O(m × n) in both time and space. For large inputs (like comparing two 10,000-line files), this is slow.

Eugene Myers published a faster algorithm in 1986 that's O(ND) in time, where D is the number of differences (additions + deletions). When the two files are similar (small D), this is dramatically faster than O(m × n). When they're very different (large D), it degrades to the same complexity as the classic algorithm.

Myers' algorithm is what git diff uses by default. It's why git diffs are fast even for large files with small changes.

The intuition is that the algorithm searches through the "edit graph" of the two sequences, finding the shortest path from the top-left to the bottom-right. Each step right is a deletion; each step down is an addition; each diagonal step is a match. The shortest path corresponds to the smallest diff.

Patience diff

A variant called "patience diff" (used by Git as an alternative) finds anchor points — lines that appear exactly once in each file — and uses those to split the problem into smaller subproblems. This produces more intuitive diffs in some cases, especially when files have been heavily reorganized.

The algorithm is named after the card game patience (solitaire), where you build sequences by patience. The same idea applies: find unique lines that can serve as anchors, then recursively diff the segments between anchors.

Patience diff produces cleaner output for reorganized code. If you've moved a function from one part of a file to another, classic diff might show it as deleted and re-added, while patience diff recognizes it as the same function moved.

Rendering the diff

Once the algorithm produces a list of hunks, the rendering layer decides how to display them. Common conventions:

Unified diff (used by git, patch): All hunks in one stream, with + and - prefixes and @@ hunk headers.
Side-by-side diff: Two columns, original on left, revised on right, with color highlighting.
Inline diff: Single column with additions and deletions inline, color-coded.

Side-by-side is the most readable for humans but takes more horizontal space. Unified diff is the most compact and is the standard format for patches.

For web-based diff tools, side-by-side is the default because screens are wide. For terminal-based tools, unified diff is standard.

Performance considerations

For typical use cases — files up to a few thousand lines — any LCS-based algorithm is fast enough. The performance cliff comes at:

Very large files. A 100,000-line file with thousands of changes is where the algorithm matters. Myers' algorithm shines here.
Many small diffs. Tools that diff files in real-time (as you type) need to be fast on small inputs. Caching the previous diff and computing only the delta helps.
Long lines. If lines are very long (e.g., minified JavaScript), character-level diff within lines is more efficient than line-level diff that treats each minified line as a unit.

For most text comparison use cases — comparing two articles, reviewing edits, checking revisions — the standard line-based LCS is more than fast enough.

Common use cases

Code review. Pull requests show diffs between branches.
Document collaboration. Google Docs and similar tools show edit history.
Configuration management. Comparing two versions of a config file.
Legal document review. Comparing two versions of a contract.
Content audit. Comparing an article before and after an editor's changes.

In all of these, the goal is the same: see what changed, quickly and clearly.

Privacy considerations

Many online diff tools send your text to a server for processing. This is fine for public content but problematic for sensitive material — contracts, NDAs, unpublished drafts, source code with proprietary logic.

A local diff tool that runs the algorithm in your browser avoids this entirely. The text never leaves your device. This is especially important for:

Legal documents. Attorney-client privilege can be compromised by uploading to a third-party service.
Source code. Proprietary code should not be sent to random websites.
Personal correspondence. Comparing versions of emails or messages should be a private operation.

TextOpal's Text Diff Checker runs the LCS algorithm locally in your browser. Two text inputs go in; a side-by-side diff comes out. No data is transmitted. The algorithm is the same one git uses; only the rendering differs.

The algorithm you can't see

Every time you see colored additions and deletions in a code review, that's Myers' algorithm or a variant at work. It's one of those foundational algorithms — like quicksort or Dijkstra's shortest path — that runs silently underneath dozens of tools you use every day.

Understanding the algorithm doesn't make you write better diffs, but it does explain why diffs sometimes look weird (a small change can produce a large diff if it shifts anchor points) and why certain tools are faster than others. The next time you run git diff, you'll know what's happening underneath.