The Prague Stringology Conference 2004
Abdullah N. Arslan and Omer Egecioglu
Algorithms for the Constrained Longest Common Subsequence Problems
| Abstract: |
| 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: |  |
 |
| PostScript |