Developer tools · Text comparison
How a Text Diff Finds Changed Lines: LCS and the Myers Algorithm
· How it works
text-diff algorithms developer-workflow
Explains the longest-common-subsequence idea behind line-based comparison and why the Myers algorithm made it fast enough to run instantly, even inside a browser tab.
Two files, one question: which lines survived? — frames comparison as finding the longest run of lines common to both versions rather than matching line numbers
Two revisions do not arrive with labels saying which lines survived. ToolAcre first splits each text into an ordered list, then searches for a long subsequence appearing in both lists in the same order. Lines outside that shared spine become additions or removals rather than guessed modifications.
The result carries original one-based positions for both sides. An unchanged row owns a number on each side, a removal only on the left, and an addition only on the right. That accounting makes the displayed story reviewable even when repeated lines give more than one plausible alignment.
Why diff works on lines, not characters — how splitting on newlines turns a text into a sequence of comparable units and why that makes prose behave differently from code
The implementation treats a complete line as its comparison unit. Newline boundaries therefore shape the result: a one-word edit inside a paragraph stored on one line replaces that whole line, while the same prose arranged sentence by sentence can isolate a much smaller region.
Line comparison is not character analysis hidden behind a different display. `splitLines` creates arrays, and the LCS table compares one line key with another. This predictable granularity suits source and configuration files, but it cannot highlight the exact letters changed inside a matched-looking replacement.
Longest common subsequence in plain terms — walks through the LCS idea on a five-line example and shows how everything outside the subsequence becomes an insertion or deletion
Imagine left lines A, B, C, D, E and right lines A, C, E. A, C and E form an ordered common subsequence. B and D fall outside it, so the result reports two removals and three unchanged rows without needing to pair either removed line with a replacement.
The table records, for every remaining pair of positions, the best shared length available from there. Reconstruction walks forward through those values. Equal keys advance both sides; otherwise the larger neighboring value decides whether to emit a left removal or a right addition.
The Myers algorithm and why speed matters — explains, without formulas, how tracing the shortest edit script keeps comparison fast on files with thousands of lines
The workbook names Myers, but `diff.js` explicitly implements plain longest-common-subsequence dynamic programming. Its comment states O(n·m) time and memory for the differing middle. Claiming Myers or shortest-edit-graph behavior would substitute a familiar algorithm for the code that actually ships.
ToolAcre limits that cost before allocation. Equal prefixes and suffixes are peeled away in linear passes, and either differing middle may contain at most 2,000 lines. The matrix is a `Uint32Array`; the documented worst permitted square occupies about sixteen megabytes rather than unbounded boxed values.
ToolAcre uses an LCS table, not the Myers algorithm named in the outline
Compare a changelog containing “Added search”, “Fixed export”, and “Updated help” with a revision that keeps the first and third entries but inserts “Added filters” before the last. The common entries anchor the path, “Fixed export” is removed, and “Added filters” is added.
The algorithm does not call that pair a modified line. Its row vocabulary is only equal, add and remove, so a textual replacement appears as one removal followed by one addition. The summary counts those operations separately and marks the texts identical only when both counts are zero.
Why two correct diffs can look different — shows how ties between equally short edit scripts explain why one tool blames a blank line and another blames a closing bracket
Repeated or interchangeable lines can produce several common subsequences of the same length. ToolAcre resolves one tie by preferring a removal when the two neighboring table values are equal. Another correct implementation may choose an addition first and present a different-looking alignment with the same edit cost.
That is why a blank line or closing brace can appear attached to a different hunk across tools. The discrepancy does not automatically mean either comparison lost content. Read the original line numbers and surrounding unchanged rows before treating presentation differences as competing factual claims.
What this does not cover — semantic or structural comparison, move detection and word-level highlighting are outside what a line-based diff computes
Nothing in this path parses syntax trees, recognizes renamed identifiers, labels moved blocks or understands prose meaning. A moved paragraph violates the shared-order requirement and can appear once as removed and once as added. The tool also does not compute character- or word-level highlights inside rows.
Those omissions are boundaries, not hidden modes. Use a language-aware reviewer for semantic claims and version control for merge history. Text diff answers the narrower question of how two ordered line sequences differ, then lets the human interpret whether those textual edits are important.
Takeaway: what the highlighted lines really mean — summarises how to read a line diff as the shortest story of edits and how ToolAcre's Text comparison runs this in your tab without uploading anything
Read green and red rows as one LCS-derived explanation, not as proof of author intent. Prefix and suffix trimming change the amount of work but not the final line accounting. Original text remains in every row even when case or whitespace options supply looser keys for matching.
The comparison executes through imported browser modules and renders with DOM text nodes; there is no conversion endpoint in the tool path. Try a five-line example, swap the sides, and download the patch-shaped output to see how direction changes additions into removals without inventing semantics.