Longest common subsequence
Given two sequences, the LCS is the longest sequence appearing in the same relative order in both — though not necessarily consecutively. ABCDE vs ACDEF have LCS ACDE. The diff algorithm derives the operation list (keep / delete / insert) from the LCS by walking both inputs and emitting whichever isn't in the common subsequence.