Вечно полезная Википедия утверждает, что diff реализует Longest Common Subsequence.
Этого не может быть. Diff, по крайней мере в режиме -y, имеет три типа отчетов: добавить, удалить и заменить. У LCS нет понятия «заменитель».
Что такое алгоритм сравнения? У меня есть причина не верить, что это расстояние Левенштейна, но я мог ошибочно проанализировать это.