The constrained longest common subsequence problem

This paper considers a constrained version of longest common subsequence problem for two strings. Given strings S-1, S-2 and P. the constrained longest common subsequence problem for S-1 and S-2 with respect to P is to find a longest common subsequence Ics of S-1 and S-2 such that P is a subsequence of this Ics. An O(r n(2)m(2)) time algorithm based upon the dynamic programming technique is proposed for this new problem, where n, in and r are lengths of S-1, S-2 and P, respectively. (C) 2003 Elsevier B.V. All rights reserved.