Fast algorithms for computing the constrained LCS of run-length encoded strings

AbstractThe constrained LCS (CLCS) problem, a recent variant of the longest common subsequence (LCS) problem, has gained much attention. Given two sequences X and Y of lengths n and m, respectively, and the constrained sequence P of length r, previous research shows that the CLCS problem can be solved by either an O(nmr)-time algorithm based upon dynamic programming (DP) techniques or an O(rRloglog(n+m))-time Hunt–Szymanski-like algorithm, where R is the total number of ordered pairs of positions at which the two strings match. In this paper, we investigate the case that X, Y and P are all in run-length encoded (RLE) format, where the numbers of runs are N, M and R, respectively. We first show that when the sequences are encoded, the CLCS problem can be solved by a simple algorithm in O(nmR+nMr+Nmr) time without decompressing the sequences. Then, we propose a more efficient algorithm with O(NMr+r×min{q1,q2}+q3) time, where q1 and q2 denote the numbers of elements in the south and east faces of the matched blocks on the first layer, respectively, and q3 denotes the number of face elements of all fully matched cuboids in the DP lattice