Finding a longest common subsequence between a run-length-encoded string and an uncompressed string

[[abstract]]In this paper, we propose an O(min {mN, Mn}) timealgorithm for finding a longest common subsequence of strings X and Y with lengths M and N, respectively, and run-length-encoded lengths in and n, respectively. We propose a new recursive formula for finding a longest common subsequence of Y and X which is in the run-length-encoded format. That is, Y = y(1)y(2) ... y(N) and X = r(1)(l1) r(2)(l2) ... r(m)(1m), where r(i) is the repeated character of run i and l(i) is the number of its repetitions. There are three cases in the proposed recursive formula in which two cases are for r(i) matching y(j). The third case is for r(i) mismatching y(j). We will look specifically at the prior two cases that r(i) matches y(j). To determine which case will be used when r(i) matches y(j), we have to find a specific value which can be obtained by using another of our proposed recursive formulas. (C) 2007 Elsevier Inc. All rights reserved.[[note]]SC