A preprocessing for approximate string matching

Kensuke Baba, Tetsuya Nakatoh, Yasuhiro Yamada, Daisuke Ikeda

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)


Approximate string matching is a basic and important concept in many applications of information retrieval. This paper proposes an algorithm for the problem of approximate string matching. The algorithm solves the match-count problem as a preprocessing. For input strings of each length n, the time complexities of the approximate string matching problem and the match-count problem are O(n2) and O(nlogn), respectively. Therefore, the computation time of the algorithm is expected to be short when the scope of search is drastically restricted by the preprocessing. This paper makes clear the relation between the solutions of the two problems.

Original languageEnglish
Title of host publicationInformatics Engineering and Information Science - International Conference, ICIEIS 2011, Proceedings
Number of pages6
EditionPART 2
Publication statusPublished - 2011
Externally publishedYes
EventInternational Conference on Informatics Engineering and Information Science, ICIEIS 2011 - Kuala Lumpur, Malaysia
Duration: Nov 14 2011Nov 16 2011

Publication series

NameCommunications in Computer and Information Science
NumberPART 2
Volume252 CCIS
ISSN (Print)1865-0929


ConferenceInternational Conference on Informatics Engineering and Information Science, ICIEIS 2011
CityKuala Lumpur


  • FFT
  • algorithm
  • approximate string matching

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics


Dive into the research topics of 'A preprocessing for approximate string matching'. Together they form a unique fingerprint.

Cite this