| 作成者 |
|
|
|
|
|
|
|
| 本文言語 |
|
| 出版者 |
|
| 発行日 |
|
| 収録物名 |
|
| 巻 |
|
| 開始ページ |
|
| 終了ページ |
|
| 出版タイプ |
|
| アクセス権 |
|
| 関連DOI |
|
| 関連URI |
|
| 関連情報 |
|
| 概要 |
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 a...lphabet. 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.続きを見る
|
Mendeley出力
