Geodesic
A new practical linear space algorithm for the longest common subsequence problem
Kybernetika, Tome 38 (2002) no. 1, p. [45]

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

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 \lbrace mp,p(n-p)\rbrace )$ 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 \lbrace mp,m\log m+p(n-p)\rbrace )$ time while preserving the linear space bound, thus solving the problem posed in [ric94,ric95]. Experimental results confirm the efficiency of our method.
Classification : 68Q25, 68W05, 68W32
Keywords: longest common subsequence problem; Rick’s algorithm 
@article{KYB_2002__38_1_a2,
     author = {Goeman, Heiko and Clausen, Michael},
     title = {A new practical linear space algorithm for the longest common subsequence problem},
     journal = {Kybernetika},
     pages = {[45]},
     publisher = {mathdoc},
     volume = {38},
     number = {1},
     year = {2002},
     mrnumber = {1899846},
     zbl = {1265.68363},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2002__38_1_a2/}
}
TY  - JOUR
AU  - Goeman, Heiko
AU  - Clausen, Michael
TI  - A new practical linear space algorithm for the longest common subsequence problem
JO  - Kybernetika
PY  - 2002
SP  - [45]
VL  - 38
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/KYB_2002__38_1_a2/
LA  - en
ID  - KYB_2002__38_1_a2
ER  - 
%0 Journal Article
%A Goeman, Heiko
%A Clausen, Michael
%T A new practical linear space algorithm for the longest common subsequence problem
%J Kybernetika
%D 2002
%P [45]
%V 38
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/KYB_2002__38_1_a2/
%G en
%F KYB_2002__38_1_a2
Goeman, Heiko; Clausen, Michael. A new practical linear space algorithm for the longest common subsequence problem. Kybernetika, Tome 38 (2002) no. 1, p. [45]. http://geodesic.mathdoc.fr/item/KYB_2002__38_1_a2/