کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950832 | 1441037 | 2017 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An acceleration of FFT-based algorithms for the match-count problem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: An acceleration of FFT-based algorithms for the match-count problem An acceleration of FFT-based algorithms for the match-count problem](/preview/png/4950832.png)
چکیده انگلیسی
The match-count problem on strings is a problem of counting the matches of characters for every possible gap of the starting positions between two strings. This problem for strings of lengths m and n (mâ¤n) over an alphabet of size Ï is classically solved in O(Ïnlogâ¡m) time using the algorithm based on the convolution theorem and a fast Fourier transform (FFT). This paper provides a method to reduce the number of computations of the FFT required in the FFT-based algorithm. The algorithm obtained by the proposed method still needs O(Ïnlogâ¡m) time, but the number of required FFT computations is reduced from 3Ï to 2Ï+1. This practical improvement of the processing time is also applicable to other algorithms based on the convolution theorem, including algorithms for the weighted version of the match-count problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 125, September 2017, Pages 1-4
Journal: Information Processing Letters - Volume 125, September 2017, Pages 1-4
نویسندگان
Kensuke Baba,