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

الأصل · EN

In this paper, we consider a generalized longest common subsequence problem with multiple substring inclusive constraints. For the two input sequences X and Y of lengths n and m, and a set of d constraints P={P₁,,Pd} of total length r, the problem is to find a common subsequence Z of X and Y including each of constraint string in P as a substring and the length of Z is maximized. A new dynamic programming solution to this problem is presented in this paper. The correctness of the new algorithm is proved. The time complexity of our algorithm is O(d2ᵈnmr). In the case of the number of constraint strings is fixed, our new algorithm for the generalized longest common subsequence problem with multiple substring inclusive constraints requires O(nmr) time and space.