קלים יפרמנקו

Let T = t₀ ... t_n-1 be a text and P = p₀ ... p_m-1 a pattern taken from some finite alphabet set Σ, and let d be a metric on Σ. We consider the problem of calculating the sum of distances between the symbols of P and the symbols of substrings of T of length m for all possible offsets. We present an ε-approximation algorithm for this problem which runs in time O(1/ε²n · polylog(n, |Σ|)). This algorithm is based on a low distortion embedding of metric spaces into normed spaces (especially, into l_∞), which is done as a preprocessing stage. The algorithm is also based on a technique of sampling.