How Diff Algorithms Find Changes: LCS Explained Simply
Most diff tools, including the classic algorithm behind tools like "git diff," work by finding the longest common subsequence (LCS) shared between two pieces of text — the largest set of words or lines that appear in the same relative order in both versions — and then treating everything in the original that isn't part of that shared subsequence as removed, and everything in the new version that isn't part of it as added, which produces the smallest, most sensible set of changes that explains the difference between the two.
This LCS-based approach is a well-established computer science technique, not something specific to any one tool.
Why finding the longest shared sequence matters
There are often many possible ways to explain how one text turned into another, but most of them would involve unnecessarily marking a lot of unchanged content as if it were removed and re-added — finding the longest common subsequence specifically minimizes that, producing the smallest, most intuitive set of actual insertions and deletions rather than an overly complicated explanation of the difference.
Why this can still occasionally produce a surprising result
When the same word or phrase appears multiple times in a text, there can be more than one valid longest common subsequence, and the algorithm's specific choice among equally long options can occasionally produce a diff that doesn't match how a person would have intuitively grouped the change, even though it's technically a correct, minimal-length diff.