Currently displaying 1 – 3 of 3

Showing per page

Order by Relevance | Title | Year of publication

A new practical linear space algorithm for the longest common subsequence problem

Heiko Goeman;  Michael Clausen — 2002

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 ≥ m , on an alphabet of size s , we first present an algorithm which determines the length p of an LCS in O ( n s + min { m p , p ( n - p ) } ) time and O ( n s ) 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 ( n s + min { m p , m log m + p ( n - p ) } ) time while preserving the linear space bound, thus solving...

Page 1

Download Results (CSV)