Faster Algorithms for Text-to-Pattern Hamming Distances

Timothy M. Chan, Ce Jin, Virginia Vassilevska Williams +1

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 Ha…