Faster Approximate Text-to-Pattern Hamming Distances via Near-Optimal Sumset EstimationResearch Paper
A text search can ask how closely a pattern agrees with each window of a longer text. The Hamming distance counts positions containing different symbols. Computing the distance at every alignment is a basic string algorithm problem, and the number of distinct symbols can grow with the input. The classical exact algorithms have approximately a three-halves…