A Generalization of FFT Algorithms for String Matching
Kensuke Baba, Yoshihito Tanaka, Tetsuya Nakatoh, Ayumi Shinohara · QIR (Kyushu University Institutional Repository) (Kyushu University) · 2003
There exists an algorithm which solves string match-ing problem with mismatches by computing a vector by the fast Fourier transformation (FFT), however, the time complexity depends on the size of the alpha-bet. Atallah et al. introduced a randomized algorithm in which the time complexity has a trade-off with the accuracy of the estimates for the vector and it was improved by Baba et al. This paper generalize these three algorithms in terms of the functions which con-vert characters into numbers. The generalization pro-vides that the exact vector is obtained by repeating the FFT computation at least σ − 1 times, where σ is the size of the alphabet. Moreover, it gives the exact variance of the estimates for the vector. 1