2002/11/08 by Lasse Bergroth, Harri Hakonen, T. Raita · 9 citations
Computer Science · Biochemistry, Genetics and Molecular Biology · Mathematics · Engineering · #Algorithms and Data Compression #Network Packet Processing and Optimization #Genomics and Phylogenetic Studies #Longest common subsequence problem #Computer science #Subsequence #Task (project management) #Algorithm #Longest increasing subsequence #Space (punctuation) #Data structure #Theoretical computer science #Mathematics #Programming language #Engineering
paper · doi:10.1109/spire.2000.878178
openalex publication_date 2002/11/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
The aim of this paper is to give a comprehensive comparison of well-known longest common subsequence algorithms (for two input strings) and study their behaviour in various application environments. The performance of the methods depends heavily on the properties of the problem instance as well as the supporting data structures used in the implementation. We want to make also a clear distinction between methods that determine the actual lcs and those calculating only its length, since the execution time and more importantly, the space demand depends crucially on the type of the task. To our knowledge, this is the first time this kind of survey has been done. Due to the page limits, the paper gives only a coarse overview of the performance of the algorithms; more detailed studies are reported elsewhere.