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=⟨x_1,\dots ,x_m⟩$ and $Y=⟨y_1,\dots ,y_n⟩$, 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=⟨z_1,\dots ,z_k⟩$ be an LCS of $X$ and $Y$, with prefixes $X_i=⟨x_1,\dots ,x_i⟩$:

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{array}{ll}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{array}$$

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.)