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 t
ext 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-cas
e 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 sm
all universal constant c and are easy reductions from the case of arbi
trary SIGMA to the case of SIGMA = (0, 1}.