Approximating Approximate Pattern Matching
share
Given a text T of length n and a pattern P of length m, the approximate pattern matching problem asks for computation of a particular distance function between P and every m-substring of T. We consider a (1±ε) multiplicative approximation variant of this problem, for ℓ_p distance function. In this paper, we describe two (1+ε)-approximate algorithms with a runtime of O(n/ε) for all (constant) non-negative values of p. For p > 1 we show a deterministic (1+ε)-approximation algorithm. Previously, such run time was known only for the case of p = 1 (ℓ_1 distances), by Gawrychowski and Uznański [ICALP 2018] and only with a randomized algorithm. For 0 < p < 1 we show a randomized algorithm for the (ℓ_p)^p distance (the p-th power of the ℓ_p distance), thereby providing a smooth tradeoff between algorithms of Kopelowitz and Porat [FOCS 2015, SOSA 2018] for Hamming distance (case of p=0) and of Gawrychowski and Uznański for ℓ_1 distance.
READ FULL TEXT