An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring exclusive constraints

In this paper, we consider a generalized longest common subsequence problem with multiple substring exclusive constraints. For the two input sequences X and Y of lengths n and m, and a set of d   constraints P={P1,…,Pd}P={P1,…,Pd} of total length r, the problem is to find a common subsequence Z of X and Y excluding each of constraint string in P as a substring and the length of Z is maximized. The problem was declared to be NP-hard [7], but we finally found that this is not true. A new dynamic programming solution for this problem is presented in this paper. The correctness of the new algorithm is proved. The time complexity of our algorithm is O(nmr)O(nmr).