An Efficient Mapping for Computing the Score of String Matching
Tetsuya Nakatoh, Kensuke Baba, Daisuke Ikeda, Yasuhiro Yamada, Sachio Hirokawa · Journal of automata, languages and combinatorics · 2005
The authors propose an efficient algorithm to solve the problem of string matching with mismatches. For a text of length n and a pattern of length m over an alphabet $\Sigma$, the problem is known to be solved in $O(|\Sigma|n\log m)$ time by computing a score by the fast Fourier transformation (FFT). Atallah et al. introduced a randomized algorithm in which the time complexity can be decreased by the trade-off with the accuracy of the estimates for the score. The algorithm in the present paper yields an estimate with smaller variance compared to the algorithm by Atallah et al. Moreover it computes the exact score in $O(|\Sigma|n\log m)$ time.