Hardness of comparing two run-length encoded strings

DOI10.1016/j.jco.2010.03.003zbMath1193.94077OpenAlexW2009278392MaRDI QIDQ990818

Ping-Hui Hsu, Kun-Mao Chao, Kuan-Yu Chen

Publication date: 1 September 2010

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

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

zbMATH Keywords

run-length encodingsequence comparisoncompressed pattern matching

Mathematics Subject Classification ID

Bounds on codes (94B65)

Related Items (5)

R\'enyi entropy and pattern matching for run-length encoded sequences ⋮ Approximation of functions on the sphere on a Sobolev space with a Gaussian measure in the probabilistic case setting ⋮ A fully compressed algorithm for computing the edit distance of run-length encoded strings ⋮ Efficient retrieval of approximate palindromes in a run-length encoded string ⋮ Gel'fand-\(N\)-width in probabilistic setting

Cites Work

• Unnamed Item
• Unnamed Item
• Simple deterministic wildcard matching
• Matching patterns in strings subject to multi-linear transformations
• Matching for run-length encoded strings
• Inplace run-length 2d compressed search.
• Approximate matching of run-length compressed strings
• On a class of \(O(n^ 2)\) problems in computational geometry
• Edit distance for a run-length-encoded string and an uncompressed string
• Finding a longest common subsequence between a run-length-encoded string and an uncompressed string
• Sequence Alignment Algorithms for Run-Length-Encoded Strings
• Generalized String Matching
• A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
• POLYGON CONTAINMENT AND TRANSLATIONAL IN-HAUSDORFF-DISTANCE BETWEEN SEGMENT SETS ARE 3SUM-HARD
• Faster algorithms for string matching with k mismatches

This page was built for publication: Hardness of comparing two run-length encoded strings