Longest common subsequence

A longest common subsequence of two finite sequences has maximum length among sequences that occur in both with their original order. Characters can be skipped; this differs from requiring a contiguous substring. For $ABCBDAB$ and $BDCABA$, $BCBA$ is a common subsequence of length four.

Let $L(i,j)$ be the optimum for the first $i$ and $j$ terms. Set $L(0,j)=L(i,0)=0$. If the final terms agree, $L(i,j)=1+L(i-1,j-1)$; otherwise $L(i,j)=\max (L(i-1,j),L(i,j-1))$. Filling the table gives $O(mn)$ time. Retaining predecessor choices reconstructs an actual subsequence, while two rows suffice if only the length is needed.