Faster Algorithms for Text-to-Pattern Hamming Distances

We study the classic Text-to-Pattern Hamming Distances problem: given a pattern P of length m and a text T of length n, both over a polynomial-size alphabet, compute the Hamming distance between P and $T[i \ldots i+m-1]$ for every shift i, under the standard Word-RAM model with $\Theta(\log n)$-bit words.•We provide an $O(n \sqrt{m})$ time Las Vegas randomized algorithm for this problem, beating the decades-old $O(n \sqrt{m \log m})$ running time [Abrahamson, SICOMP 1987]. We also obtain a deterministic algorithm, with a slightly higher $O\left(n \sqrt{m}(\log m \log \log m)^{1 / 4}\right)$ running time. Our randomized algorithm extends to the k-bounded setting, with running time $O\left(n+\frac{n k}{\sqrt{m}}\right)$, removing all the extra logarithmic factors from earlier algorithms [Gawrychowski and Uznanski, ICALP 2018; Chan, Golan, Kociumaka, Kopelowitz and Porat, STOC 2020].•For the $(1+\varepsilon)$-approximate version of Text-to-Pattern Hamming Distances, we give an $\widetilde{O}\left(\varepsilon^{-0.93} n\right)$ time Monte Carlo randomized algorithm (where $\widetilde{O}$ hides poly-logarithmic factors), beating the previous $\widetilde{O}\left(\varepsilon^{-1} n\right)$ running time [Kopelowitz and Porat, FOCS 2015; Kopelowitz and Porat, SOSA 2018].Our approximation algorithm exploits a connection with 3SUM, and uses a combination of Fredman’s trick, equality matrix product, and random sampling; in particular, we obtain new results on approximate counting versions of 3 SUM and Exact Triangle, which may be of independent interest. Our exact algorithms use a novel combination of hashing, bit-packed FFT, and recursion; in particular, we obtain a faster algorithm for computing the sumset of two integer sets, in the regime when the universe size is close to quadratic in the number of elements. We also prove a fine-grained equivalence between the exact Text-to-Pattern Hamming Distances problem and a range-restricted, counting version of 3 SUM.