A New Efficient Algorithm for Computing the Longest Common Subsequence |
| |
Authors: | Costas S Iliopoulos M Sohel Rahman |
| |
Affiliation: | (1) Algorithm Design Group, Department of Computer Science, King’s College London, Strand, London, WC2R 2LS, England, UK |
| |
Abstract: | The Longest Common Subsequence (LCS) problem is a classic and well-studied problem in computer science. The LCS problem is a common task in DNA sequence
analysis with many applications to genetics and molecular biology. In this paper, we present a new and efficient algorithm
for solving the LCS problem for two strings. Our algorithm runs in O(ℛlog log n+n) time, where ℛ is the total number of ordered pairs of positions at which the two strings match.
Preliminary version appeared in 24].
C.S. Iliopoulos is supported by EPSRC and Royal Society grants.
M.S. Rahman is supported by the Commonwealth Scholarship Commission in the UK under the Commonwealth Scholarship and Fellowship
Plan (CSFP) and is on Leave from Department of CSE, BUET, Dhaka-1000, Bangladesh. |
| |
Keywords: | Longest common subsequence Algorithms Strings |
本文献已被 SpringerLink 等数据库收录! |
|