How Diff Tools Find Changes: The LCS Algorithm Explained
Paste two blocks of text into a diff tool and it highlights, as if by magic, exactly which lines were removed and which were added. But underneath, it's running a classic dynamic-programming (DP) problem from any algorithms course: LCS (Longest Common Subsequence). By digging into the actual source code of the text diff checker, this guide walks through how diff separates "same" from "changed," and why the tool caps input at 3,000 lines.
1. The core problem: you have to find what's the same before you can see what's different
Intuitively, you might think comparing two texts line by line would work, but the moment a single line is inserted or deleted in the middle, every line after it shifts position, and a naive line-number comparison breaks. So diff algorithms flip the approach. They first find the longest sequence of lines that appear in both texts in the same relative order (the LCS), and classify any line not in that LCS as either "added" or "removed." A line that belongs to the LCS still counts as "unchanged" even if its position shifted, as long as the relative order is preserved.
2. Reading the actual code: the DP table and backtracking
The text diff checker's lcs(a, b) function takes two line arrays, a and b, and builds a 2D array dp of size (m+1)×(n+1). dp[i][j] represents "the LCS length between the first i lines of a and the first j lines of b." When two lines match, the cell takes the diagonal value plus 1; when they don't, it takes the larger of the value above or to the left. After the table is filled, the algorithm backtracks from the bottom-right corner to the top-left: a diagonal step where the lines match means "unchanged," a move straight up means "removed," and a move straight left means "added." This entire process operates strictly at the line level — the text is split into an array via split('\n') and compared element by element, so even if only a few words change within a single line, that entire line is shown as "removed, then added."
3. Why the 3,000-line limit exists
The DP table's size is (original line count + 1) × (modified line count + 1). If both texts are 3,000 lines, the table has roughly 9 million cells (3,001 × 3,001). This is a fundamental limitation of the classic LCS implementation, whose time and space complexity are both O(m×n) — memory needs grow quadratically as line count increases. The tool's MAX_LINES = 3000 cap, which rejects comparisons beyond that, isn't an arbitrary restriction; it's a direct consequence of keeping a 2D array manageable within a single browser tab's memory.
4. How this differs from Git's Myers algorithm
Git's default git diff also compares at the line level — the common belief that "Git works character by character while this tool works line by line" isn't accurate. The real differences are twofold. First, Git uses the more sophisticated Myers algorithm to find the shortest edit script, and its running time scales with the size of the actual changes (D), making it much faster on large files with few changes. This tool's O(m×n) DP, by contrast, scales with the size of the files themselves regardless of how much actually changed, putting it at a disadvantage for large files. Second, Git can drop down to word- or character-level granularity with flags like --word-diff and --color-words, while this tool only supports line-level comparison with no separate word or character mode. Neither tool detects "moves" (renames/relocations) by default, either — if a line is deleted from one spot and reappears verbatim somewhere else, it's shown as a separate "removed" and "added" rather than a "move."
5. A 3-line example showing how matching actually works
Suppose the original and modified texts look like this. The LCS is the 1st and 3rd lines ("apple" and "banana"), and only the 2nd line is replaced.
| Original | Modified | Diff result |
|---|---|---|
| apple | apple | unchanged |
| strawberry | (none) | removed (red) |
| (none) | grape | added (green) |
| banana | banana | unchanged |
"Strawberry" and "grape" look like a change that happened at the same spot, but from the LCS's perspective they're completely unrelated: one independent removal and one independent addition. This result is also summarized as added/removed/unchanged line counts in the stats bar at the top. If you need a different flavor of diff, purpose-built tools for structured data — like JSON diff or the CSV diff checker — will give more accurate results for their respective formats.
6. Want to know how similar two documents are overall?
Diff shows you exactly which lines changed, but it can't answer "how similar are these two documents overall?" — that calls for a different metric. For plagiarism checks or translation review, where you need an overall similarity score, the text similarity checker is the better tool to pair with this one.
FAQ
Q. Does the LCS algorithm always produce a diff result that "feels" natural to a human?
Not always. LCS mathematically finds only "the longest common subsequence," and when multiple subsequences of the same maximum length exist, the choice between them affects the result. Most of the time this matches human intuition, but text with a lot of repeated lines can produce matches you wouldn't expect.
Q. If two lines differ only in case, are they shown as "changed"?
By default, yes. Turning on the "Ignore case" option in the text diff checker converts both arrays to lowercase right before comparison, so lines that differ only in case are treated as identical.
Q. Can text over 3,000 lines not be compared at all?
Correct — because of the O(m×n) memory limitation, this tool refuses to run the comparison and shows a warning if either the original or the modified text exceeds 3,000 lines. For larger files, it's safer to split the text into sections and compare them separately, or use a dedicated version-control tool like Git.
Q. Can it detect when only a few words change within a single line?
Since this tool only compares at the line level, a partial change within a line is shown as that entire line being "removed and added." To highlight exactly which words changed, you'd need Git or a dedicated code-comparison tool that supports word-diff.