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

(10)

• Relative widths of the function classes L₂(T) defined by a linear differential operator in L_q(T)
• Fast algorithms for computing the constrained LCS of run-length encoded strings
• scientific article; zbMATH DE number 7561345 (Why is no real title available?)
• Parallel comparison of run-length-encoded strings on a linear systolic array
• Resequencing a set of strings based on a target string
• A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings
• Hardness of comparing two run-length encoded strings
• Computing the longest common subsequence of two run-length encoded strings
• Sequence Alignment Algorithms for Run-Length-Encoded Strings
• Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard

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)