An extension of the FFT-based algorithm for the match-count problem to weighted scores

Kensuke Baba

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


The match-count problem on strings is the basic problem of counting the matches of characters between two strings for every possible alignment. The problem is classically computed in O(σ n log m) time using a fast Fourier transform (FFT) for two strings of lengths m and n (m ≤ n) over an alphabet of size σ. This paper extends the target of this FFT-based algorithm to a weighted version of the problem, which computes the sum of similarities between characters instead of the number of matches. The algorithm extended in this paper can solve the weighted match-count problem in O(dn log m) time by mapping characters to numerical vectors of dimensionality d. This paper also evaluates the usefulness of the extended algorithm by applying it to plagiarism detection in documents. The experimental results show that the proposed algorithm is applicable to general vector representation of words and that the obtained plagiarism detection method can extremely reduce the processing time with a slight decrease of accuracy from the method based on the normal match-count problem.

Original languageEnglish
Pages (from-to)S97-S100
JournalIEEJ Transactions on Electrical and Electronic Engineering
Publication statusPublished - Dec 2017
Externally publishedYes


  • convolution
  • match-count problem
  • plagiarism detection
  • string matching
  • vector representation of words

ASJC Scopus subject areas

  • Electrical and Electronic Engineering


Dive into the research topics of 'An extension of the FFT-based algorithm for the match-count problem to weighted scores'. Together they form a unique fingerprint.

Cite this