TY - JOUR
T1 - A fast and practical bit-vector algorithm for the Longest Common Subsequence problem
AU - Crochemore, M
AU - Iliopoulos, C S
AU - Pinzon, Y J
AU - Reid, J F
PY - 2001/12/31
Y1 - 2001/12/31
N2 - This paper presents a new practical bit-vector algorithm for solving the well-known Longest Common Subsequence (LCS) problem. Given two strings of length rn and n, n greater than or equal to m, we present an algorithm which determines the length p of an LCS in O(nm/w) time and O(m/w) space, where tv is the number of bits in a machine word. This algorithm can be thought of as column-wise "parallelization" of the classical dynamic programming approach. Our algorithm is very efficient in practice, where computing the length of an LCS of two strings can be done in linear time and constant (additional/working) space by assuming that m less than or equal to w. (C) 2001 Elsevier Science B.V All rights reserved.
AB - This paper presents a new practical bit-vector algorithm for solving the well-known Longest Common Subsequence (LCS) problem. Given two strings of length rn and n, n greater than or equal to m, we present an algorithm which determines the length p of an LCS in O(nm/w) time and O(m/w) space, where tv is the number of bits in a machine word. This algorithm can be thought of as column-wise "parallelization" of the classical dynamic programming approach. Our algorithm is very efficient in practice, where computing the length of an LCS of two strings can be done in linear time and constant (additional/working) space by assuming that m less than or equal to w. (C) 2001 Elsevier Science B.V All rights reserved.
UR - http://www.scopus.com/inward/record.url?scp=0035980874&partnerID=8YFLogxK
U2 - 10.1016/S0020-0190(01)00182-X
DO - 10.1016/S0020-0190(01)00182-X
M3 - Article
VL - 80
SP - 279
EP - 285
JO - INFORMATION PROCESSING LETTERS
JF - INFORMATION PROCESSING LETTERS
IS - 6
ER -