= Longest common subsequence
= LCS
{c}
{synonym}
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.
Back to article page
