Advanced Search

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\ge 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)\left\}\right)$ time and $O\left(ns\right)$ 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,mlogm+p(n-p)\left\}\right)$ time while preserving the linear space bound, thus solving...