What a diff actually decides
The hard part of a diff is not spotting a changed line: it is knowing which line in the first text corresponds to which line in the second, because a document that had a paragraph inserted near the top is not a document in which everything after it changed. A diff that pairs badly shows a hundred changed lines where a human sees an insertion.
This page compares with **patience diff**, the algorithm `git diff --patience` uses. It looks for the units that appear exactly once on each side - a line that occurs once in both texts is almost always the same line - takes the longest run of those that is in the same order on both sides, and uses them as anchors. Everything between two anchors is compared again by the same rule, recursively.