Fully Incremental LCS Computation

摘要

Sequence comparison is a fundamental task in pattern matching. Its applications include file comparison, spelling correction, information retrieval, and computing (dis)similarities between biological sequences. A common scheme for sequence comparison is the longest common subsequence (LCS) metric. This paper considers the fully incremental LCS computation problem as follows: For any strings A, B and characters a,b, compute LCS(aA,B), LCS(A,bB), LCS(Aa,B), and LCS(A,Bb), provided that L = LCS(A,B) is already computed. We present an efficient algorithm that computes the four LCS values above, in O(L) or O(n) time depending on where a new character is added, where n is the length of A. Our algorithm is superior in both time and space complexities to the previous known methods.