Longest Common Subsequence in Sublinear Space

Abstract

We present the first $\mathrm{o}(n)$-space polynomial-time algorithm for computing the length of a longest common subsequence. Given two strings of length $n$, the algorithm runs in $\mathrm{O}(n^3)$ time with $\mathrm{O}\left(\frac{n{\log }^{1.5}n}{2^{\sqrt{\log n}}}\right)$ bits of space.

6 pages, 2 figures