Longest Common Subsequence

Diff is fundamentally about finding the LONGEST COMMON SUBSEQUENCE (LCS) — same characters in the same order, but not necessarily contiguous.

A: "ABCBDAB"
B: "BDCAB"
LCS: "BCAB" or "BDAB" (length 4)

Once you have the LCS, the diff is:

• DELETE = chars in A not in LCS
• INSERT = chars in B not in LCS
• KEEP = LCS chars

DP:

To recover the actual LCS sequence, backtrack through the DP table from dp[n][m].

Edit distance and LCS are related: edit_dist(a, b) = len(a) + len(b) - 2 * lcs(a, b) when only insertions/deletions are allowed (no substitutions).