Finding a longest common subsequence between a run-length-encoded string and an uncompressed string

DOI10.1016/J.JCO.2007.06.003MaRDI QIDQ2483205zbMATH OpenOpenAlexFDO

Authors Jia-Jie Liu, Yue-Li Wang, R. C. T. Lee

Publication date 28 April 2008

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jco.2007.06.003

zbMATH Keywords

longest common subsequencerun-length encodingstring compression

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32) Decoding (94B35)

Recommendations

• A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings
• Computing the longest common subsequence of two run-length encoded strings
• Matching for run-length encoded strings
• Longest common subsequence between run-length-encoded strings: a new algorithm with improved parallelism
• Fast algorithms for computing the constrained LCS of run-length encoded strings

Cites work

• A fast algorithm for computing longest common subsequences
• Algorithms for the Longest Common Subsequence Problem
• Longest common subsequence between run-length-encoded strings: a new algorithm with improved parallelism
• Matching for run-length encoded strings
• Sparse Dynamic Programming for Longest Common Subsequence from Fragments
• Sparse dynamic programming I

Cited in

(11)

• Resequencing a set of strings based on a target string
• Sequence Alignment Algorithms for Run-Length-Encoded Strings
• Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard
• Fast algorithms for computing the constrained LCS of run-length encoded strings
• Computing the longest common subsequence of two run-length encoded strings
• Sketching, streaming, and fine-grained complexity of (weighted) LCS
• Relative widths of the function classes L₂(T) defined by a linear differential operator in L_q(T)
• The generalized constrained longest common subsequence in the run-length encoded format
• Parallel comparison of run-length-encoded strings on a linear systolic array
• A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings
• Hardness of comparing two run-length encoded strings

This page was built for publication: Finding a longest common subsequence between a run-length-encoded string and an uncompressed string

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