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

Optimal Substructure

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