The generalized constrained longest common subsequence in the run-length encoded format

DOI10.1016/J.IC.2025.105311MaRDI QIDQ6966437zbMATH OpenFDO

Authors En-An Song, Chang-Biau Yang, Kuo-Tsung Tseng

Publication date 27 June 2025

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IC.2025.105311

zbMATH Keywords

constrained longest common subsequence with substring exclusiondynamic programminglongest common subsequencerun-length encoded stringstate transition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms on strings (68W32)

Cites work

• A dynamic programming solution to a generalized LCS problem
• A fast algorithm for computing longest common subsequences
• A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings
• A linear space algorithm for computing maximal common subsequences
• A longest common subsequence algorithm suitable for similar text strings
• A simple algorithm for the constrained sequence problems
• ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS
• Algorithms for the Longest Common Subsequence Problem
• An algorithm and applications to sequence alignment with weighted constraints
• An improved algorithm for computing the edit distance of run-length coded strings
• Bit-parallel algorithm for the constrained longest common subsequence problem
• Edit distance of run-length encoded strings.
• Efficient algorithms for the longest common subsequence problem with sequential substring constraints
• Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion
• Efficient string matching
• Fast algorithms for computing the constrained LCS of run-length encoded strings
• Fast Pattern Matching in Strings
• Faster space-efficient STR-IC-LCS computation
• Faster STR-EC-LCS computation
• Faster STR-IC-LCS computation via RLE
• Finding a longest common subsequence between a run-length-encoded string and an uncompressed string
• Introduction to algorithms.
• Matching for run-length encoded strings
• New efficient algorithms for the LCS and constrained LCS problems
• On the generalized constrained longest common subsequence problems
• Quadratic-time algorithm for a string constrained LCS problem
• The constrained longest common subsequence problem
• The longest common subsequence problem revisited
• The String-to-String Correction Problem
• Two algorithms for LCS consecutive suffix alignment

This page was built for publication: The generalized constrained longest common subsequence in the run-length encoded format

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