An Efficient Algorithm for String Matching with Mismatches
Tetsuya Nakatoh, Kensuke Baba, Yasuhiro Yamada, Daisuke Ikeda · 2003
The problem to find out a pattern from the string is called String matching problem. That has a wide application range, such as text search, search form the database and an information extraction from Web. Specially, String matching with mismatches problem is more difficult problem than String matching problem. We propose a new efficient algorithm to solve String matching with mismatches problem fast by utilizing fast Fourier transformation (FFT). That does not restrict the number of mismatches. That is a randomized algorithm, and its time complexity is , where is the number of randomly sampled estimations and its value is in the range of to . We can compute an exact score vector with . Exactly, our algorithm can be deterministic, too. We can choose a balance of time complexity and precision freely.