RLE edit distance in near optimal time

Raphaël Clifford, Paweł Gawrychowski, Tomasz Kociumaka +2

We show that the edit distance between two run-length encoded strings of compressed lengths $m$ and $n$ respectively, can be computed in $\mathcal{O}(mn\log (mn))$ time. This improv…