A Simple Polynomial Time Algorithm for the Generalized LCS Problem with Multiple Substring Exclusive Constraints

摘要

In this paper, we present a simple polynomial time algorithm for a generalized longest common subsequence problem with multiple substring exclusion constraints. Given two sequences X and Y of lengths m and n, respectively, and a set of constraint strings P of total length r, we are to find a common subsequence z of X and Y which excludes each of strings in P as a substring and the length of z is maximized. The problem was declared to be NP-hard, but we finally found that this is not true. A new polynomial time solution for this problem is presented in this paper. The correctness of the new algorithm is proved. The time complexity of our algorithm is analyzed.