Approximating text-to-pattern Hamming distances
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 …