title: Edit distance of run-length encoded strings
abstract: Let X and Y be two run-length encoded strings, of encoded lengths k and l, respectively. We present a simple O(|X|l+|Y|k) time algorithm that computes their edit distance
keyphrases: edit distance run-length encoded strings encoded lengths algorithm computation time