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

In this paper, we propose an O(min{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=y1y2⋯yN and , where ri is the repeated character of run i and li is the number of its repetitions. There are three cases in the proposed recursive formula in which two cases are for ri matching yj. The third case is for ri mismatching yj. We will look specifically at the prior two cases that ri matches yj. To determine which case will be used when ri matches yj, we have to find a specific value which can be obtained by using another of our proposed recursive formulas.