Longest Common Subsequence Problem for Run-Length-Encoded Strings

In this paper, we present a new and efficient algorithm for solving the Longest Common Subsequence (LCS) problem between two run-length-encoded (RLE) strings. Suppose Ŷ and ^X are two RLE strings having length ^k and ^l respectively. Also assume that Y and X are the two uncompressed versions of the two RLE strings Ŷ and ^X having length k and ` respectively. Then, our algorithm runs in O((^k+ ^l)+Rlog log(^k^l)+Rloglogω) time, where ω = k + l and R is the total number of ordered pairs of positions at which the two RLE strings match. Our algorithm outperforms the best algorithms for the same problem in the literature.