| 作成者 |
|
|
|
|
|
|
|
|
|
| 本文言語 |
|
| 出版者 |
|
| 発行日 |
|
| 収録物名 |
|
| 巻 |
|
| 開始ページ |
|
| 終了ページ |
|
| 出版タイプ |
|
| アクセス権 |
|
| 関連DOI |
|
|
|
| 関連URI |
|
|
|
| 関連情報 |
|
|
|
| 概要 |
This paper proposes 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 Σ, the problem is known to be solv...ed in O(|Σnlogm|)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 that the algorithm by Atallah et al., moreover, and computes the exact score in O(|Σ|nlogm)time. The present paper also gives two methods to improve the algorithm and an exact estimation of the variance of the estimates for the score. Keywords: string matching with mismatches, FFT, convolution, deterministic algorithm, randomized algorithm.続きを見る
|
Mendeley出力
