Longest Common Subsequence

Problem description

A sequence Z is a subsequence of another sequence X if all the elements in Z also appear in order in X. Notably, the elements do not need to be consecutive.

In the longest-common-subsequence problem (LCS), we wish to find a maximum-length common subsequence of X and Y.

Approach: dynamic programming

Consider $X=\langle x_{1},x_{2},\ldots ,x_{m}\rangle$ and $Y=\langle y_{1},y_{2},\ldots ,y_{n}\rangle$, and let $Z=\langle z_{1},z_{2},\ldots ,z_{k}\rangle$ be an LCS of $X$ and $Y$.

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}$.

If $x_{m}\neq y_{n}$ and $Z_{k}\neq x_{m}$, then $Z$ is an LCS of $X_{m-1}$ and $Y$.

If $x_{m}\neq y_{n}$ and $Z_{k}\neq y_{n}$, then $Z$ is an LCS of $X$ and $Y_{n-1}$.

Subproblems

It is clear from the above that there are three subproblems to examine:

1. $LCS(X_{m-1},Y_{n-1})$
2. $LCS(X_{m},Y_{n-1})$
3. $LCS(X_{m-1},Y_{n})$

Let us have $c[i,j]$ be the length of the LCS for $X_{i}$ and $Y_{j}$. We have

$c[i,j]={\begin{cases}0&i=0andj=0\\c[i-1,j-1]+1&x_{i}=y_{i}\\max(c[i-1,j],c[i-1,j])&x_{i}\neq y_{i}\end{cases}}$