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 paper: |  |
 |
| PostScript |