An algorithm for matching run-length coded strings

DOI10.1007/BF02243873MaRDI QIDQ685867zbMATH OpenOpenAlexFDO

Authors Horst Bunke, János Csirik

Publication date 20 December 1993

Published in Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02243873

zbMATH Keywords

longest common subsequencetime complexitystring matchingrun-length coded strings

Mathematics Subject Classification ID

Dynamic programming (90C39) Prefix, length-variable, comma-free codes (94A45) Parallel algorithms in computer science (68W10)

Recommendations

• Edit distance of run-length encoded strings.
• Edit distance for a run-length-encoded string and an uncompressed string
• A fully compressed algorithm for computing the edit distance of run-length encoded strings
• Approximate matching of run-length compressed strings
• A fully compressed algorithm for computing the edit distance of run-length encoded strings

Cites work

• scientific article; zbMATH DE number 1142294 (Why is no real title available?)
• scientific article; zbMATH DE number 1516705 (Why is no real title available?)
• A fast algorithm for computing longest common subsequences
• A faster algorithm computing string edit distances
• Algorithms for approximate string matching
• An \(O(ND)\) difference algorithm and its variations
• The String-to-String Correction Problem

Cited in

(12)

• A GENERALIZED MAPPING OF 2-D ARRAY PROCESSOR TO LINEAR ARRAY PROCESSOR AND ITS APPLICATIONS
• scientific article; zbMATH DE number 7561710 (Why is no real title available?)
• A fast algorithm for stereo matching
• An improved algorithm for computing the edit distance of run-length coded strings
• Edit distance of run-length encoded strings.
• Hardness of comparing two run-length encoded strings
• An improved algorithm for solving the banded cyclic string-to-string correction problem
• Edit distance for a run-length-encoded string and an uncompressed string
• Sequence Alignment Algorithms for Run-Length-Encoded Strings
• Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard
• Sequence matching with binary codes
• A decision procedure for string to code point conversion

This page was built for publication: An algorithm for matching run-length coded strings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685867)