Approximating text-to-pattern Hamming distances

We revisit a fundamental problem in string matching: given a pattern of length m and a text of length n , both over an alphabet of size σ, compute the Hamming distance (i.e., the number of mismatches) between the pattern and the text at every location. Several randomized (1+ε)-approximation algorithms have been proposed in the literature (e.g., by Karloff (Inf. Proc. Lett., 1993), Indyk (FOCS 1998), and Kopelowitz and Porat (SOSA 2018)), with running time of the form O (ε − O (1) n log n log m ), all using fast Fourier transform (FFT). We describe a simple randomized (1+ε)-approximation algorithm that is faster and does not need FFT. Combining our approach with additional ideas leads to numerous new results (all Monte-Carlo randomized) in different settings:

Authors

• Timothy M. Chan
• Shay Golan 0001
• Tomasz Kociumaka
• Tsvi Kopelowitz
• Ely Porat

Keywords

• Hamming distance
• pattern matching
• property testing
• sampling
• streaming
• sublinear