Longest Common Subsequence Problem

Definition

Longest Common Subsequence Problem

Given two strings $S=s_1{s}_2\dots s_m$ and $T=t_1{t}_2\dots t_n$ over an alphabet $\Sigma$. The longest common subsequence problem asks for the length $\ell$ of a longest string that is a subsequence of both $S$ and $T$.

Input: $(S,T)\in {\Sigma }^{\ast }\times {\Sigma }^{\ast }$
Output: the length $\ell$ of the longest string that is a subsequence of both $S$ and $T$

Algorithms

Brute-force Algorithm

Definition

Brute-force Algorithm (Longest Common Subsequence)

Given two strings $S$ and $T$, the brute-force algorithm for the longest common subsequence problem enumerates every choice of positions in $S$, tests whether the resulting subsequence also occurs in $T$, and returns the greatest accepted length:

$$\max \{|A|:A\text{ is a subsequence of both }S\text{ and }T\}.$$

There are $2^{|S|}$ choices of positions: each position is either retained or omitted. Different choices can produce the same string when letters repeat.

Link to original

Dynamic Programming Algorithm

Definition

Dynamic Programming Algorithm (Longest Common Subsequence)

Given two strings $S$ and $T$, the dynamic programming algorithm for the longest common subsequence problem computes the optimum for pairs of prefixes and reuses those results.

Use zero-based indices. For a string $P$, $P[i]$ is the letter at index $i$, and $P[a..b]$ is the substring from index $a$ to index $b$, including both endpoints.

Let $\ell (i,j)$ be the length of an LCS of the prefixes $S[\mathrm{0..}i]$ and $T[\mathrm{0..}j]$.

If one prefix is empty, no non-empty common subsequence is possible:

$$\ell (i,-1)=\ell (-1,j)=0.$$

For non-empty prefixes, compare their last letters:

$$\ell (i,j)=\{\begin{array}{ll}\ell (i-1,j-1)+1& \text{if }S[i]=T[j]\\ \max \{\ell (i,j-1),\ell (i-1,j)\}& \text{if }S[i]\ne T[j]\end{array}$$

Return $\ell (|S|-1,|T|-1)$. Memoisation computes each required state at most once.

Link to original

Examples

$S=\text{algorithm}$, $T=\text{complexity}$

The longest common subsequences are $\text{oit},\text{lit}$ of length 3.

$S=\text{abc},T=\text{ac}$

The longest common subsequence is $\text{ac}$ with length $\ell =2$.

$S=\text{abcd},T=\text{acbd}$

Both $\text{abd}$ and $\text{acd}$ are longest common subsequences, each of length $\ell =3$.

$S=\text{abcdef},T=\text{acf}$

The longest common subsequence is $\text{acf}$ with length $\ell =3$.

$S=\text{abc},T=\text{def}$

No character appears in both strings. The only common subsequence is the empty string $\epsilon$, so $\ell =0$.