Algorithms for the constrained longest common subsequence problems
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 lcs of S-1 and S-2 which contains P as a subsequence. We present an algorithm which improves the time complexity of the problem from the previously known 0(rn(2)m(2)) to 0(rnm) where r, n, and m axe the lengths of P, S-1, and S-2, 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 less than a given parameter d. For the latter problem, we propose an algorithm whose time complexity is O(drnm).
longest common subsequence edit distance constrained subsequence dynamic programming