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

摘要

In this paper, we propose an O(mn{mN, Mn}) time algorithm for finding a longest common subsequence of strings X and Y with lengths M and N, respectively, and run-length-encoded lengths m 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_1Y_2…y_n and X=r_1~1 r_2~(l2)… r~(lm)_m, where r_1 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.