Solution: Longest Common Subsequence of Two Sequences

Solution

Consider a longest common subsequence $C = (c_1 , \ldots, c_p )$ specified by indices $1≤i_1 <i_2 <\ldots<i_p ≤n$ and $1≤j_1 <j_2 <\ldots<j_p ≤ m$ (therefore, for every $1≤q≤p, a_{i_{q}}=b_{j_{q}} =c_q$).

• Last symbols of $A$ and $B$ appear in $C$. In this case, $i_ p =n$ and $j_p =m$. Then, $(c_1,\ldots,c_{p−1})$ is a longest common subsequence of $(a_1,\ldots,a_{n−1})$ and $(b_1,\ldots,b_{m−1})$.

• At least one of the last symbols of $A$ and $B$ doesn’t appear in $C$. In this case, either $i_p < n$ or $j_p < m$. Then, $(c_1,\ldots,c_{p−1})$ lies entirely in either $(a_1,\ldots,a_{n−1})$ or $(b_1,\ldots,b_{m−1})$.

This way, we reduce the problem for the initial strings $A$ and $B$ to the same problem on their prefixes. This motivates the following definition: $LCS(i,j)$ is the length of the longest common subsequence of $A[1\ldots i]$ and $B[1\ldots j]$. The discussion above implies that this function satisfies the following recurrence relation:

$$LCS(i , j) = \text{max} \begin{cases} LCS(i-1 , j) \\ LCS(i , j-1) \\ LCS(i-1 , j-1)+1 & \text{if }~~ A[i]=B[j] \end{cases}$$

The base case for this recurrence relation is $i = 0$ or $j = 0$:

$$LCS(0,j) = LCS(i,0) = 0.$$

The resulting algorithm is shown below. Its running time is $O(nm)$.

---

 $LCS(A[1\ldots n],B[1 \ldots m])$:
 $table ←$ 2d array of size $(n + 1) × (m + 1)$
 $table[i][0] ← 0$ and $table[0][j] ← 0$ for all $i,j$
 for all $i,j$ for $i$ from $1$ to $n$:
 for $j$ from $1$ to $m$:
  $table[i][j] ← table[i − 1][j]$
  $table[i][j] ← max(table[i][j], table[i][j − 1])$
  if $A[i] = B[j]$:
   $table[i][j] ← max(table[i][j], table[i − 1][j − 1] + 1)$
 return $table[n][m]$

---

Stop and think: Can you reduce the Longest Common Subsequence Problem to the Edit Distance Problem?