Given strings S1, S2, and P, the constrained longest common subsequence problem for S1
and S2 with respect to P is to find a longest common subsequence lcs of S1 and S2 which
contains P as a subsequence. We present an algorithm which improves the time complexity
of the problem from the previously known O (rn2m2) to O (rnm) where r, n, and m are the
lengths of P, S1, and S2, respectively. As a generalization of this, we extend the definition of
the problem so that the lcs sought contains a subsequence whose edit distance from P is …

Given strings S1, S2, and P, the constrained longest common subsequence problem for S1
and S2 with respect to P is to find a longest common subsequence lcs of S1 and S2 such
that P is a subsequence of this lcs. We present an algorithm which improves the time
complexity of the problem from the previously known O (rn2m2) to O (rnm) where r, n, and m
are the lengths of P, S1, and S2, respectively. As a generalization of this, we extend the
definition of the problem so that the lcs sought contains a subsequence whose edit distance …