Recurrence
dp[i][j] = if s[i]==t[j] then dp[i-1][j-1]+1 else max(dp[i-1][j], dp[i][j-1]).
Advertisement
Reconstruction
Trace back from dp[N][M]: match → include char + move (i-1, j-1); else move to whichever has larger dp value.
Advertisement
Hunt-Szymanski
O((N + R) log N) where R = number of matches. Faster when strings have few matching char pairs.
LCS ↔ Edit distance
Special case of edit distance. Distance = N + M - 2·LCS if only insert/delete allowed.