[Solved]: Find longest common subsequence in limited space

Problem Detail: 

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

Asked By : Mike

Answered By : A.Schulz

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12045