An almost-linear time and linear space algorithm for the longest common subsequence problem

DOI10.1016/j.ipl.2005.01.002zbMath1192.68827OpenAlexW1987087299MaRDI QIDQ1041737

Frank K. Hwang, Jun-Yi Guo

Publication date: 4 December 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2005.01.002

zbMATH Keywords

algorithmsprimal-dual algorithmlongest common subsequence

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Related Items (4)

A linear space algorithm for computing a longest common increasing subsequence ⋮ Efficient merged longest common subsequence algorithms for similar sequences ⋮ Computing the longest topological common subsequence of a symbol-wise totally ordered directed acyclic graph and a sequence ⋮ A data structure for substring-substring LCS length queries

Cites Work

• Unnamed Item
• Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings
• Generalized sequence alignment and duality
• A linear space algorithm for computing maximal common subsequences
• A fast algorithm for computing longest common subsequences
• Algorithms for the Longest Common Subsequence Problem

This page was built for publication: An almost-linear time and linear space algorithm for the longest common subsequence problem