algorithm - linux diff -y 的算法是什么？

Question

永远有用的维基百科声称 diff 实现了最长公共(public)子序列。

这不可能。 Diff，至少在 -y 模式下，具有三种类型的报告:添加、删除和替换。 LCS没有任何“替代”的概念。

diff的算法是什么？我有理由不相信这是 Levenshtein 距离，但我可能分析错了。

Answer 1

This answer(作者 ioplex)说 GNU diff 实现了 Eugene Myers 的“O(ND) diff 算法”。