Efficient algorithms for enumerating maximal common subsequences of two strings

DOI10.1016/J.TCS.2025.115360MaRDI QIDQ6969918zbMATH OpenFDO

Authors Miyuji Hirota, Yoshifumi Sakai

Publication date 19 June 2025

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115360

zbMATH Keywords

enumerationlongest common subsequencemaximal common subsequence

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Cites work

• A compact DAG for storing and searching maximal common subsequences
• A dynamic programming solution to a generalized LCS problem
• 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
• A simple algorithm for the constrained sequence problems
• An \(O(ND)\) difference algorithm and its variations
• An almost-linear time and linear space algorithm for the longest common subsequence problem
• Enumeration of maximal common subsequences between two strings
• scientific article; zbMATH DE number 30301 (Why is no real title available?)
• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings
• Maximal common subsequence algorithms
• Maximal common subsequence algorithms
• Maximal common subsequences and minimal common supersequences
• McDag: indexing maximal common subsequences in practice
• On the generalized constrained longest common subsequence problems
• Optimal bounds for the predecessor problem and related problems
• Quadratic-time algorithm for a string constrained LCS problem
• The Complexity of Some Problems on Subsequences and Supersequences
• The constrained longest common subsequence problem
• 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: Efficient algorithms for enumerating maximal common subsequences of two strings

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