How Are Two Texts Compared? The Diff Algorithm (LCS) Explained

Where Does the Need to Compare Two Texts Come From?

Comparing two versions of a text by hand, reading line by line to work out what changed, is slow and error-prone. What changed in a code file since the previous commit, which sentences were added in the new draft of a contract, which line was deleted from a configuration file — diff algorithms are used to answer these questions quickly and reliably. The word "diff" is short for "difference", and it describes the comparison operation that automatically detects the difference between two texts.

The output of a diff is simple: which lines stayed the same between the two texts, which were removed and which were newly added. But the logic running underneath to produce that simple output is a classic computer science problem: finding the way to turn one text into the other with the fewest possible changes.

LCS: The Longest Common Subsequence Approach

Most diff tools — from the classic Unix diff command to git diff, from code review tools to text comparators — are conceptually based on the idea of the Longest Common Subsequence (LCS for short). LCS aims to find the longest subsequence common to two sequences (here, lists of lines) with their order preserved. The lines in the subsequence do not have to be adjacent; what matters is that the order between them is not broken.

In practice the algorithm places the lines of the two texts into a table (a dynamic programming matrix) and compares each pair of lines to compute which lines occur in both texts in a common order. Once that common order has been found, the rest is easy: lines that are not part of the common subsequence were either removed from the old text or added to the new one.

How are added, deleted and unchanged lines determined?

Once the LCS has been found, the diff tool scans both texts from start to end: if a line is part of the common subsequence in both texts, it is marked as unchanged. A line that is not part of the common subsequence and appears only in the original text is marked as deleted (usually shown in red), while one that appears only in the new text is marked as added (usually shown in green). If the content of a line has changed partially — for example if a single word was updated — then, because diff works line by line, this is generally shown as that line being deleted entirely and re-added in its updated form; the algorithm compares the whole line as a single unit, not the words inside it.

Diff on a Simple Example

Take the two short texts below; the left one is the original and the right one the modified version.

When we compare these two texts line by line, the resulting difference is this: Hello world and Unchanged line appear in the same order in both texts, so they are part of the LCS and are marked as unchanged. This is an example line exists only in the original text, so it counts as deleted, and the This is an updated line that takes its place exists only in the new text, so it counts as added. In the same way, Last line has been removed and A new line was added has newly joined the text. The diff output therefore consists of 2 unchanged, 2 deleted and 2 added lines — exactly the view you see as red/green lines in a code review.

Ways of Presenting Diff Output

A diff result is usually presented in two different forms. The side-by-side view shows the two texts in two adjacent columns, as in the table above, and makes the comparison visually easier. A unified diff, on the other hand, shows everything in a single column, using a space at the start of unchanged lines, a - at the start of deleted lines and a + at the start of added lines; the default output of the git diff command and .patch files use this format.

In the unified diff format each change block is marked with a header of the form @@ -a,b +c,d @@ indicating its position in the file; the numbers there show the line numbers of the change in the original and new file and how many lines it spans. This format is a practical way to share changes by email or apply them to a file automatically (patching), and it sits in the infrastructure of many version control systems.

Where Is Diff Used?

• Code review: Seeing which lines changed in a pull request lets you review by focusing only on the changes instead of rereading the whole file.
• Git and version control: Commands such as git diff and git log -p compute and display the difference between commits with LCS logic; that is how every past change to a file can be traced.
• Document and content tracking: Used to find the differences between two drafts of a contract, an article or the text of a web page.
• Auditing configuration files: Detecting which lines changed between the previous and the new state of server or application settings makes debugging easier.

Common Mistakes and Misunderstandings

The difference between character-, word- and line-based diff

Diff algorithms can work at different levels: line-based (the most common, and the default in git and most diff tools), word-based and character-based. A line-based diff marks a whole line as "changed" even if only a single character in it changed; that can make the output hard to read when a long line has a small change in it. Word- or character-based diff tools highlight exactly which word or letter changed within a line, but the computation cost is higher.

Whitespace sensitivity

Diff tools are whitespace sensitive by default: an extra space at the end of a line, a tab character replaced by spaces or a different line ending (CRLF on Windows, LF on Unix) can show a line as "changed" even when the content is actually the same. This can produce false positive changes, especially in files edited on different operating systems or saved with different editor settings.

Shifted lines can produce a misleading diff

Because LCS looks for line-based matches, when a block of code is merely moved to a different place in the file, most diff tools show it not as "moved" but as deleted from the old position and added at the new one. In the same way, when a new line is added at the top of a file, the algorithm can sometimes find a different match than expected and mark more lines as "changed" than necessary. This is not a bug in the algorithm but a natural limitation of line-based comparison, and it should be kept in mind when interpreting diff output.

Using an LCS-based comparison tool instead of hunting for the difference between two texts by hand is both faster and more reliable. The tool below runs the line-based LCS logic described above directly in your browser; the texts you enter are not sent to any server.