Matching for run-length encoded strings

DOI10.1006/jcom.1998.0493zbMath0921.68041OpenAlexW1968328322MaRDI QIDQ1288529

Gad M. Landau, Steven S. Skiena, Alberto Apostolico

Publication date: 11 May 1999

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

Full work available at URL: https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=2354&context=cstech

zbMATH Keywords

pattern matching

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

Related Items (21)

Speeding up HMM decoding and training by exploiting sequence repetitions ⋮ LCS\(k\): a refined similarity measure ⋮ Dynamic RLE-Compressed Edit Distance Tables Under General Weighted Cost Functions ⋮ A multiobjective optimization algorithm for the weighted LCS ⋮ Longest common subsequence between run-length-encoded strings: a new algorithm with improved parallelism ⋮ R\'enyi entropy and pattern matching for run-length encoded sequences ⋮ Parallel comparison of run-length-encoded strings on a linear systolic array ⋮ Straight-line programs: a practical test (extended abstract) ⋮ Theoretical lower bound for border length minimization problem ⋮ Unified compression-based acceleration of edit-distance computation ⋮ A fully compressed algorithm for computing the edit distance of run-length encoded strings ⋮ Sequence Alignment Algorithms for Run-Length-Encoded Strings ⋮ Fast algorithms for computing the constrained LCS of run-length encoded strings ⋮ Computing similarity of run-length encoded strings with affine gap penalty ⋮ Weighted LCS ⋮ Finding a longest common subsequence between a run-length-encoded string and an uncompressed string ⋮ A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings ⋮ Unnamed Item ⋮ Hardness of comparing two run-length encoded strings ⋮ Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard ⋮ Edit distance of run-length encoded strings.

Cites Work

• An improved algorithm for computing the edit distance of run-length coded strings
• A faster algorithm computing string edit distances
• An information-theoretic lower bound for the longest common subsequence problem
• The set-set LCS problem
• A linear space algorithm for computing maximal common subsequences
• Bounds on the Complexity of the Longest Common Subsequence Problem
• On the Set LCS and Set-Set LCS Problems

This page was built for publication: Matching for run-length encoded strings