LCS is the longest sequence of characters that appears in the same relative order (but not necessarily contiguously) in two strings. It's the mathematical core of diff, of git's minimum-edit view, of DNA alignment, and of every "your version vs mine" three-way merge. Fill the DP table below cell-by-cell to see how.
dp[i][j] = A[i-1] === B[j-1] ? dp[i-1][j-1] + 1 : max(dp[i-1][j], dp[i][j-1]).
Diagonal ↖ means "matched a character", up ↑ or left ← means "extend without matching".
The O(n·m) DP table is the standard textbook algorithm. Where diff actually lives: edit distance and LCS are duals — edit distance = n + m − 2·|LCS| when the only ops are insert and delete. Unix diff uses the Myers algorithm (1986), which is O((n+m)·D) where D is the edit distance — a huge speed-up when files barely changed, but the ideas trace back to this same table. Hunt-Szymanski is another classic when one input has few duplicate lines. Backtracking from the bottom-right corner recovers an LCS, but ties in the max mean there can be many equally-long ones — try the "ABCBDAB / BDCABA" preset (4 LCS variants). This same table also underlies Needleman-Wunsch global-alignment scoring in bioinformatics.