Visual Text & Code Diff Checker

The Architecture of Diff Algorithms: Longest Common Subsequence & Myers O(ND)

Finding differences between two textual files is one of the most fundamental operations in software version control. From git diff and code reviews on GitHub to automated merge conflict resolution, diff engines rely on formal discrete mathematics to compute the shortest sequence of additions and deletions required to transform one string into another.

1. The Longest Common Subsequence (LCS) Problem

Given two sequences of lines $A = (a_1, a_2, \dots, a_n)$ and $B = (b_1, b_2, \dots, b_m)$, the Longest Common Subsequence (LCS) is the longest sequence of lines that appears in both $A$ and $B$ in the same relative order, though not necessarily contiguously.

Every element in $A$ not present in the LCS represents a deletion (-). Every element in $B$ not present in the LCS represents an addition (+). The minimum edit script that transforms $A$ into $B$ is strictly complementary to their LCS.

2. Eugene Myers' O(ND) Difference Algorithm

Published in 1986 by Eugene Myers, the $O(ND)$ difference algorithm is the industry-standard algorithm used in GNU diff and Git. It frames the difference problem as finding the shortest path through an edit grid graph:

• Moving right represents a deletion from sequence $A$.
• Moving down represents an insertion into sequence $B$.
• Moving diagonally (at no cost) represents identical lines shared by both sequences.

Myers' algorithm explores paths with cost $D$ (where $D$ is the number of edits) in increasing order. In typical code diffs where two revisions are 95%+ identical, $D$ is tiny, allowing the algorithm to execute in near-linear time $O(ND)$ rather than traditional dynamic programming $O(N \times M)$ time.

3. The Unified Diff Format (RFC 3986 & GNU Patch)

Standardized by GNU diff, the Unified Diff format records file changes cleanly without duplicating identical context throughout:

--- a/src/auth.js
+++ b/src/auth.js
@@ -10,6 +10,7 @@
 function verifySession(token) {
   if (!token) return false;
+  if (isTokenExpired(token)) return false;
   return db.users.find(token.uid);
 }

The chunk header @@ -10,6 +10,7 @@ indicates that the hunk starts at line 10 with 6 lines in the original file, and starts at line 10 with 7 lines in the modified file. Developers can apply this unified patch directly via patch -p1 < changes.patch or git apply changes.patch.

4. Whitespace & Line Ending Normalization

One of the most frequent sources of spurious diff noise is inconsistent line endings (Windows CRLF \r\n vs Unix LF \n) or trailing spaces. This tool includes automated whitespace normalization, stripping trailing whitespace and normalizing line breaks to avoid false positives during code comparison.

5. Frequently Asked Questions (FAQ)

Are my confidential files or source code sent to your servers?

No. All line tokenization, LCS calculations, and visual highlight rendering execute 100% locally within your browser. No source text or diff results are ever transmitted across the network.

Can I export a unified patch from this tool?

Yes. Clicking "Copy Unified Patch" generates a standard GNU/Git patch with --- original and +++ modified chunk headers that you can save as a .patch or .diff file.

How does "Ignore Whitespace" work?

When enabled, the comparison algorithm trims leading and trailing spaces and condenses consecutive internal spaces before checking equality. Lines that differ only by indentation or trailing spaces will be marked as unchanged.