Efficient Polynomial-Time Algorithms for the Constrained LCS Problem with Strings Exclusion

In this paper, we revisit a recent variant of the longest common subsequence (LCS) problem, the string-excluding constrained LCS (STR-EC-LCS) problem, which was first addressed by Chen and Chao [8]. Given two sequences X and Y of lengths m and n, respectively, and a constraint string P of length r, we are to find a common subsequence Z of X and Y which excludes P as a substring and the length of Z is maximized. In fact, this problem cannot be correctly solved by the previously proposed algorithm. Thus, we give a correct algorithm with O(mnr) time to solve it. Then, we revisit the STR-EC-LCS problem with multiple constraints {P1, P2, · · · , Pk}. We propose a polynomial-time algorithm which runs in O(mnR) time, where R = ∑k i=1 |Pi|, and thus it overthrows the previous claim of NP-hardness