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

DOI10.1016/J.JCO.2007.06.003zbMATH Open1279.68371OpenAlexW2056989509MaRDI QIDQ2483205FDOQ2483205

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

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

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)

Cites Work

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

Cited In (10)

• Relative widths of the function classes \(L_2(T)\) defined by a linear differential operator in \(L_q(T)\)
• Fast algorithms for computing the constrained LCS of run-length encoded strings
• Title not available (Why is that?)
• Parallel comparison of run-length-encoded strings on a linear systolic array
• Resequencing a set of strings based on a target string
• Computing the longest common subsequence of two run-length encoded strings
• A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings
• Hardness of comparing 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)