Approximate Matching for Run-Length Encoded Strings Is 3SUM-Hard

In this paper, we consider a commonly used compression scheme called run-length encoding (abbreviated RLE). We provide lower bounds for problems of approximately matching two RLE strings. Specifically, we show that the wildcard matching and k-mismatches problems for RLE strings are 3SUM-hard. For two RLE strings of m and n runs, such a result implies that it is very unlikely to devise an o(mn)-time algorithm for either problem. We then propose an O(mn + p log m)-time sweep-line algorithm for their combined problem, i.e. wildcard matching with mismatches, where p <= mn is the number of matched or mismatched runs. Furthermore, the problem of aligning two RLE, strings is also shown to be 3SUM-hard.