A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings

Let X and Y be two strings of lengths n and m, respectively, and k and l, respectively. be the numbers of runs in their corresponding run-length encoded forms. We propose a simple algorithm for computing the longest common subsequence of two given strings X and Y in O(kl + min{p(1),p(2)}) time, where p1 and p2 denote the numbers of elements in the bottom and right boundaries of the matched blocks, respectively. It improves the previously known time bound O(min{nl, km}) and outperforms the time bounds O(kl log kl) or O((k + l + q) log (k + l + q)) for some cases, where q denotes the number of matched blocks. (C) 2008 Elsevier B.V. All rights reserved.