The Prague Stringology Club Workshop '99

H. Goeman and M. Clausen

A New Practical Linear Space Algorithm for the Longest Common Subsequence Problem

Abstract:
This paper deals with a new practical method for solving the longest common subsequence (LCS) problem. Given two strings of lengths m and n, n >= m, on an alphabet of size s, we first present an algorithm which determines the length p of an LCS in O(ns+min(mp,p(n-p))) time and O(ns) space. This result has been achieved before [ric94, ric95], but our algorithm is significantly faster than previous methods. We also provide a second algorithm which generates an LCS in O(ns+min(mp,m log(m)+p(n-p))) time while preserving the linear space bound, thus solving the problem posed in [ric94, ric95]. Experimental results confirm the efficiency of our method.

Download article: Article in PostScript Article in PDF
 PostScript   PDF