Efficient algorithms for the longest common subsequence problem with sequential substring constraints

Abstract: In this paper, we generalize the inclusion constrained longest common subsequence (CLCS) problem to the hybrid CLCS problem which is the combination of the sequence inclusion CLCS and the string inclusion CLCS, called the sequential substring constrained longest common subsequence (SSCLCS) problem. In the SSCLCS problem, we are given two strings and of lengths and , respectively, formed by alphabet and a constraint sequence formed by ordered strings with total length . The problem is that of finding the longest common subsequence of and containing as substrings and with the order of the ’s retained. This problem has two variants, depending on whether the strings in cannot overlap or may overlap. We propose algorithms with and time for the two variants. For the special case with one or two constraints, our algorithm runs in or time, respectively—an order faster than the algorithm proposed by Chen and Chao. [Copyright &y& Elsevier]