title: What is the algorithm of linux diff -y?
body: <p>The ever-helpful Wikipedia claims that diff implements Longest Common Subsequence.</p>
  
  <p>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'.</p>
  
  <p>What is the algorithm of diff? I have reason to not believe that it is Levenshtein distance, but I might have misanalyzed this.</p>