An acceleration of FFT-based algorithms for the match-count problem

Kensuke Baba

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)1-4
Number of pages4
JournalInformation Processing Letters
Publication statusPublished - Sept 1 2017
Externally publishedYes


  • Algorithms
  • Convolution
  • FFT
  • Match-count problem
  • Processing time

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications


Dive into the research topics of 'An acceleration of FFT-based algorithms for the match-count problem'. Together they form a unique fingerprint.

Cite this