A lower-variance randomized algorithm for approximate string matching ?
We study a classic problem in pattern matching: estimating the score vector of matches between a text string and a pattern string. We propose a randomized algorithm with estimation variance that is much better than the previously best algorithm with the same running time. The algorithm is also simpler compared with the previous algorithm.
randomized algorithms approximate string matching convolution fft