A`EDA Group Department of CSE, BUET, Dhaka-1000, Bangladesh

---

Abstract—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 ^ Y and ^X are two RLE strings having length ^k and ^` respectively. Also assume that Y and X are the two uncompressed versions of the two RLE strings ^ Y and ^X having length k and ` respectively. Then, our algorithm runs in O((^k+ ^`)+Rlog log(^k^`)+Rlog log !) time, where ! = k + ` 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.

Index Terms—RLE, LCS, vEB Tree, Bounded Heap, Matched Block Calculation.

[PDF]

Cite: Shegufta Bakht Ahsan, Syeda Persia Aziz, M. Sohel Rahman, "Longest Common Subsequence Problem for Run-Length-Encoded Strings," Journal of Computers vol. 9, no. 8, pp. 1769-1775, 2014.