We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS.
- Authors
Arslan, Abdullah N.; EĞecioĞlu, Ömer
- 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 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 less than a given parameter d. For the latter problem, we propose an algorithm whose time complexity is O(drnm).
- Subjects
ALGORITHMS; HEURISTIC; COMPUTATIONAL complexity; AUTOMATION; OPERATIONS research; MACHINE theory
- Publication
International Journal of Foundations of Computer Science, 2005, Vol 16, Issue 6, p1099
- ISSN
0129-0541
- Publication type
Article
- DOI
10.1142/S0129054105003674