INCREMENTAL STRING COMPARISON

The problem of comparing two sequences A and B to determine their long est common subsequence (LCS) or the edit distance between them has bee n much studied. In this paper we consider the following incremental ve rsion of these problems: given an appropriate encoding of a comparison between A and B, can one incrementally compute the answer for A and b B, and the answer for A and Bb with equal efficiency, where b is an ad ditional symbol? Our main result is a theorem exposing a surprising re lationship between the dynamic programming solutions for two such ''ad jacent'' problems. Given a threshold k on the number of differences to be permitted in an alignment, the theorem leads directly to an O(k) a lgorithm for incrementally computing a new solution from an old one, a s contrasts the O(k(2)) time required to compute a solution from scrat ch. We further show, with a series of applications, that this algorith m is indeed more powerful than its nonincremental counterpart. We show this by solving the applications with greater asymptotic efficiency t han heretofore possible. For example, we obtain O(nk) algorithms for t he longest prefix approximate match problem, the approximate overlap p roblem, and cyclic string comparison.