# Find longest common subsequence in limited space

Given three strings $x$, $y$, and $z$ over an arbitrary finite alphabet, I need to determine their longest common subsequence (LCS).

Example: A longest common subsequence of bandana, cabana, and magazine is aan.

I'm trying to find an algorithm which uses $O(|x|\cdot |y| \cdot |z|)$ space where $|s|$ denotes the length of the string $s$.

## 1 Answer

The standard dynamic programming algorithm for the LCS$(x,y)$ problem runs in time $O(|x|\cdot |y|)$. Simply speaking you fill out a $|x| \times |y|$ table $T$ using the recursion $$T[i,j] = \begin{cases} 0 & \mbox{ if }\ i = 0 \mbox{ or } j = 0 \\ T(i-1,j-1) + 1 & \mbox{ if } x_i = y_j \\ \max\{T[i,j-1],T[i-1,j]\} & \mbox{ if } x_i \ne y_j \\ \end{cases}.$$

A natural extension of this recursion leads to an algorithm that fills out an $|x|\times |y|\times |z|$ table and computes the LCS of three strings.

Notice that you can improve the required space even further (while keeping the asymptotic running time) using Hirschberg's extension.