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

The 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 0(nmr)-time algorithm based upon dynamic programming (DP) techniques or an 0(r R log log(n + m))-time Hunt-Szymanski-like algorithm, where,R is the total r umber 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 0(nmR + nMr + Nmr) time without decompressing the sequences. Then, we propose a more efficient algorithm with 0(NMr + r x min{q(1), q(2)} + q(3)) time, where q(1) and q(2) denote the numbers of elements in the south and east faces of the matched blocks on the first layer, respectively, and q(3) denotes the number of face elements of all fully matched cuboids in the DP lattice. (C) 2012 Elsevier B.V. All rights reserved.