A fast and practical bit-vector algoithm for the Longest Common Subsequence problem

摘要

This paper presents a new practical bit-vector algorithm for solving the well-known Longest Common Subsequence (LCS) problem. Given two strings of length m and n, n≥m, we present an algorithm which determines the length of an LCS in O(nm/w) time an O(m/w) space, where w 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≤w.