FAST LINEAR-SPACE COMPUTATIONS OF LONGEST COMMON SUBSEQUENCES

Space saving techniques in computations of a longest common subsequence (LCS) of two strings are crucial in many applications, notably, in molecular sequence comparisons. For about ten years, however, the only linear-space LCS algorithm known required time quadratic in the length of the input, for all inputs. This paper reviews linear-space LCS computations in connection with two classical paradigms originally designed to take less than quadratic time in favorable circumstances. The objective is to achieve the space reduction without alteration of the asymptotic time complexity of the original algorithm. The first one of the resulting constructions takes time O(n(m-l)), and is thus suitable for cases where the LCS is expected to be close to the shortest input string. The second takes time O(ml log(min[s,m,2n/l])) and suits cases where one of the inputs is much shorter than the other. Here m and n (m less-than-or-equal-to n) are the lengths of the two input strings, l is the length of the longest common subsequences and s is the size of the alphabet. Along the way, a very simple 0(m(m-l)) time algorithm is also derived for the case of strings of equal length.