Longest common subsequence

The problem

A subsequence drops zero or more elements from a sequence *without reordering* the rest (ACE is a subsequence of ABCDE). Given two sequences $X=\langle x_1,\dots,x_m\rangle$ and $Y=\langle y_1,\dots,y_n\rangle$, the longest common subsequence (LCS) is a longest sequence that is a subsequence of both. It powers diff tools, version control, and DNA alignment.

Optimal substructure (Theorem 14.1)

Let $Z=\langle z_1,\dots,z_k\rangle$ be an LCS of $X$ and $Y$, with prefixes $X_i = \langle x_1,\dots,x_i\rangle$:

1. If $x_m = y_n$, then $z_k = x_m = y_n$ and $Z_{k-1}$ is an LCS of $X_{m-1}$ and $Y_{n-1}$.
2. If $x_m \ne y_n$ and $z_k \ne x_m$, then $Z$ is an LCS of $X_{m-1}$ and $Y$.
3. If $x_m \ne y_n$ and $z_k \ne y_n$, then $Z$ is an LCS of $X$ and $Y_{n-1}$.

These three cases are exhaustive — a matched pair must be the LCS's last element; an unmatched last element can be dropped from one side.

The recurrence

Let $c[i,j]$ be the length of an LCS of $X_i$ and $Y_j$: $$c[i,j] = \begin{cases} 0 & i=0 \text{ or } j=0 \\ c[i-1,j-1]+1 & i,j>0 \text{ and } x_i = y_j \\ \max(c[i-1,j],\,c[i,j-1]) & i,j>0 \text{ and } x_i \ne y_j \end{cases}$$

The diagonal-vs-max decision is the whole algorithm. Match $\Rightarrow$ go diagonal $+1$. Mismatch $\Rightarrow$ take the better of dropping $x_i$ (up) or $y_j$ (left).

Worked example: X = ABCBDAB, Y = BDCABA

Fill the $(m{+}1)\times(n{+}1)$ table in row-major order, so $c[i-1,j-1]$, $c[i-1,j]$, $c[i,j-1]$ are always ready before $c[i,j]$. The final cell gives length 4; reconstructing back from it yields BCBA (other length-4 LCSs like BDAB exist — any one is correct).

Cost

$\Theta(mn)$ subproblems, $O(1)$ work each $\Rightarrow \Theta(mn)$ time and $\Theta(mn)$ space. Reconstruction is $O(m+n)$: from $c[m,n]$, on a match emit $x_i$ and step diagonally; otherwise step toward the larger neighbor. (CLRS stores arrows in a $b$ table; you can instead re-derive the direction from the $c$ values, as the code below does.)