The Prague Stringology Conference 2004

Abdullah N. Arslan and Omer Egecioglu

Algorithms for the Constrained Longest Common Subsequence Problems

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 from P is less than a given parameter D. For the latter problem, we propose an algorithm whose time complexity is O(drnm).

Download paper: Article in PostScript Article in PDF
 PostScript   PDF