Approximating general metric distances between a pattern and a text
Ely Porat, Klim Efremenko · 2008
Let T = t0... tn−1 be a text and P = p0... pm−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 ε 2 n · polylog(n, |Σ|)). 1