What is the algorithm of linux diff -y?

Question

The ever-helpful Wikipedia claims that diff implements Longest Common Subsequence.

This cannot be so. Diff, at least in -y mode, has three types of report: add, remove, and substitute. LCS does not have any concept of 'substitute'.

What is the algorithm of diff? I have reason to not believe that it is Levenshtein distance, but I might have misanalyzed this.

Answer 1

This answer (by ioplex) says that GNU diff implements "O(ND) diff algorithm" by Eugene Myers.