Approximating Approximate Pattern Matching

Abstract

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 \emph{distance} function between $P$ and every $m$-substring of $T$. We consider a $(1\pm \epsilon )$ multiplicative approximation variant of this problem, for ${\ell }_p$ distance function. In this paper, we describe two $(1+\epsilon )$-approximate algorithms with a runtime of $\tilde{O}(\frac{n}{\epsilon })$ for all (constant) non-negative values of $p$. For constant $p\ge 1$ we show a deterministic $(1+\epsilon )$-approximation algorithm. Previously, such run time was known only for the case of ${\ell }_1$ distance, by Gawrychowski and Uznański [ICALP 2018] and only with a randomized algorithm. For constant $0\le p\le 1$ we show a randomized algorithm for the ${\ell }_p$, 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 ${\ell }_1$ distance.