An algorithm for matching run-length coded strings

DOI10.1007/BF02243873zbMATH Open0780.94004OpenAlexW14091147MaRDI QIDQ685867FDOQ685867

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

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

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)

Cites Work

• The String-to-String Correction Problem
• A faster algorithm computing string edit distances
• An \(O(ND)\) difference algorithm and its variations
• A fast algorithm for computing longest common subsequences
• Title not available (Why is that?)
• Algorithms for approximate string matching
• Title not available (Why is that?)

Cited In (12)

• A GENERALIZED MAPPING OF 2-D ARRAY PROCESSOR TO LINEAR ARRAY PROCESSOR AND ITS APPLICATIONS
• Title not available (Why is that?)
• A fast algorithm for stereo matching
• Edit distance of run-length encoded strings.
• An improved algorithm for computing the edit distance of run-length coded 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)