| Creator |
|
|
|
|
|
|
|
| Language |
|
| Publisher |
|
| Date |
|
| Source Title |
|
| Vol |
|
| First Page |
|
| Last Page |
|
| Publication Type |
|
| Access Rights |
|
| Related DOI |
|
| Related URI |
|
| Relation |
|
| Abstract |
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.show more
|
Export Mendeley
BTNS03