On the generalized constrained longest common subsequence problems
Journal
Journal of Combinatorial Optimization
Journal Volume
21
Journal Issue
3
Pages
383-392
Date Issued
2011
Author(s)
Abstract
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. © 2009 Springer Science+Business Media, LLC.
Type
journal article