A new practical linear space algorithm for the longest common subsequence problem
This paper deals with a new practical method for solving the longest common subsequence (LCS) problem. Given two strings of lengths and , , on an alphabet of size , we first present an algorithm which determines the length of an LCS in time and 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 time while preserving the linear space bound, thus solving...