2
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.