FAST ALGORITHMS FOR APPROXIMATELY COUNTING MISMATCHES

Given a text string T is-an-element-of SIGMA(n) and a pattern string P is-an-element-of SIGMA(m), for each i = 1, 2,...,n-m + 1 define f(i) to be the number of mismatches when the pattern is aligned below the text and starts in position i of the text. The fastest known algorithm to compute all the f(i)'s when the alphabet is arbitrary has worst-case time exceeding n square-root m. For any epsilon > 0, we give simple randomized and deterministic algorithms that compute g(i) such that f(i) less-than-or-equal-to g(i) less-than-or-equal-to f(i)(1 + epsilon) for all i. The algorithms run in time O((n/epsilon2) log(c)m) for a small universal constant c and are easy reductions from the case of arbitrary SIGMA to the case of SIGMA = (0, 1}.