New efficient algorithms for the LCS and constrained LCS problems |
| |
Authors: | Costas S Iliopoulos |
| |
Affiliation: | Algorithm Design Group, Department of Computer Science, King's College London, Strand, London WC2R 2LS, England, UK |
| |
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(Rloglogn+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 O(pRloglogn+n) in the worst case, where p is the length of the third string. |
| |
Keywords: | Algorithms Combinatorial problems Longest common subsequence |
本文献已被 ScienceDirect 等数据库收录! |
|