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

Abstract: In this paper, we propose an time algorithm for finding a longest common subsequence of strings and with lengths and , respectively, and run-length-encoded lengths and , respectively. We propose a new recursive formula for finding a longest common subsequence of and which is in the run-length-encoded format. That is, and , where is the repeated character of run and is the number of its repetitions. There are three cases in the proposed recursive formula in which two cases are for matching . The third case is for mismatching . We will look specifically at the prior two cases that matches . To determine which case will be used when matches , we have to find a specific value which can be obtained by using another of our proposed recursive formulas. [Copyright &y& Elsevier]