Abdullah N. Arslan and Omer Egecioglu
Algorithms for the Constrained Longest Common Subsequence Problems
Abstract: |
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} 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(rn^{2}m^{2}) to O(rnm) where r, n, and m are 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). |
Download paper: | ||
PostScript |