Solution: Longest Common Subsequence of Three Sequences

Solution

Let $LCS(i,j,k)$ be the maximum length of a common subsequence of $A[1\ldots i], B[1\ldots j],$ and $C[1\ldots k]$. Then,

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

Base case:

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

The corresponding algorithm has running time $O(nmk)$.

Code

Here is the code for the algorithm discussed above.