On the generalized constrained longest common subsequence problems

We investigate four variants of the longest common subsequence problem. Given two sequences X, Y and a constrained pattern P of lengths m, n, and ρ, respectively, the generalized constrained longest common subsequence (GC‐LCS) problems are to find a longest common subsequence of X and Y including (or excluding) P as a subsequence (or substring). We propose new dynamic programming algorithms for solving the GC‐LCS problems in O(mn ρ) time. We also consider the case where the number of constrained patterns is arbitrary.