Linear-space LCS enumeration for two strings

DOI10.4230/LIPICS.CPM.2025.2MaRDI QIDQ7299433zbMATH OpenFDO

Authors Yoshifumi Sakai

Publication date 17 July 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.CPM.2025.2

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Cites work

• A fast algorithm for computing longest common subsequences
• A faster algorithm computing string edit distances
• A linear space algorithm for computing maximal common subsequences
• A longest common subsequence algorithm suitable for similar text strings
• A new efficient algorithm for computing the longest common subsequence
• An almost-linear time and linear space algorithm for the longest common subsequence problem
• Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings
• Quadratic conditional lower bounds for string problems and dynamic time warping
• The longest common subsequence problem revisited
• The String-to-String Correction Problem
• Tight hardness results for LCS and other sequence similarity measures

This page was built for publication: Linear-space LCS enumeration for two strings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7299433)