Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
428165 | Information Processing Letters | 2008 | 5 Pages |
Abstract
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{p1,p2}) 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(kllogkl) or O((k+l+q)log(k+l+q)) for some cases, where q denotes the number of matched blocks.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics