| タイトル | A Generalization of FFT Algorithms for String Matching |
| 本文（外部サイト） | https://catalog.lib.kyushu-u.ac.jp/opac_download_md/15559/BTNS03.pdf |
| 参考URL | http://hdl.handle.net/2324/15559 |
| 著者（英） | Baba, Kensuke; Tanaka, Yoshihito; Nakatoh, Tetsuya; Shinohara, Ayumi |
| 発行日 | 2009-10-15 |
| 発行機関など | Kyushu University |
| 刊行物名 | Proceedings of the International Symposium on Information Science and Electrical Engineering |
| 巻 | 2003 |
| 開始ページ | 191 |
| 終了ページ | 194 |
| 刊行年月日 | 2003-11 |
| 言語 | eng |
| 内容記述 | There exists an algorithm which solves string matching problem with mismatches by computing a vector by the fast Fourier transformation (FFT), however, the time complexity depends on the size of the alphabet. 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 convert characters into numbers. The generalization provides 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. |
| 資料種別 | Conference Paper |
| 著者版フラグ | author |
