Abstract
In this paper, we study the classic and well-studied longest common subsequence (LCS) problem and a recent variant of it, namely the constrained LCS (CLCS) problem. In the CLCS problem, the computed LCS must also be a supersequence of a third given string. In this paper, we first present an efficient algorithm for the traditional LCS problem that runs in O(R log logn + n) time, where R is the total number of ordered pairs of positions at which the two strings match and n is the length of the two given strings. Then, using this algorithm, we devise an algorithm for the CLCS problem having time complexity 0(pR log log n + n) in the worst case, where p is the length of the third string. (c) 2007 Elsevier B.V. All rights reserved
Original language | English |
---|---|
Pages (from-to) | 13 - 18 |
Number of pages | 6 |
Journal | INFORMATION PROCESSING LETTERS |
Volume | 106 |
Issue number | 1 |
DOIs | |
Publication status | Published - 31 Mar 2008 |