Longest Common Subsequence Problem

computation

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

Brute-Force Algorithm

Brute-Force Algorithm

A brute-force approach enumerates all $2^m$ subsequences of $S$, checks for each whether it is also a subsequence of $T$, and keeps the maximum length found.

int lcs_bruteforce(String S, String T)
    int best := 0
    for each subsequence A of S:
        if is_subsequence(A, T):
            best := max(best, |A|)
    return best

Checking whether $A$ is a subsequence of $T$ takes $O(|T|)$ time by scanning $T$ left to right.

Time complexity: $O(2^m\cdot n)$ where $m=|S|$ and $n=|T|$.

Recursive Algorithm

Recursive Dynamic Programme

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

Now consider an LCS $X$ of $S[\mathrm{0..}i]$ and $T[\mathrm{0..}j]$.

• If $X$ ends with $S[i]$ and $S[i]=T[j]$, then the last letters can be matched. This gives $\ell (i-1,j-1)+1$.
• If $X$ ends with $S[i]$ but $S[i]\ne T[j]$, then $T[j]$ is not used. This case is covered by $\ell (i,j-1)$.
• If $X$ does not end with $S[i]$, then $S[i]$ is not used. This case is covered by $\ell (i-1,j)$.

In the matching case, taking the matching last letters dominates dropping one of them. Hence the recurrence simplifies to:

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

int lcs_rec(int i, int j)
    if i < 0 or j < 0:
        return 0
    if memo[i][j] is known:
        return memo[i][j]
    if S[i] == T[j]:
        memo[i][j] := lcs_rec(i-1, j-1) + 1
    else:
        memo[i][j] := max(lcs_rec(i, j-1), lcs_rec(i-1, j))
    return memo[i][j]

Correctness follows from the case split above. The diagram shows the two behaviours of a recursive call.

With memoisation or bottom-up table filling, there are $|S||T|$ values to compute, and each value takes $O(1)$ work after its dependencies are known.

Time complexity: $O(|S||T|)$. Without memoisation, the recursion tree can be exponential because the same subproblems reappear.

Examples

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