Kybernetika

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)\})$ time and $O(ns)$ space. This result has been achieved before \cite{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 \cite{ric94,ric95}. Experimental results confirm the efficiency of our method.