Hardness of comparing two run-length encoded strings
From MaRDI portal
Publication:990818
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
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