Approximate string matching: A simpler faster algorithm

Richard Cole, Ramesh Hariharan

Research output: Contribution to journalArticlepeer-review

Abstract

We give two algorithms for finding all approximate matches of a pattern in a text, where the edit distance between the pattern and the matching text substring is at most k. The first algorithm, which is quite simple, runs in time O(nk3/m + n + m) on all patterns except k-break periodic strings (defined later). The second algorithm runs in time O(nk4/m + n + m) on k-break periodic patterns. The two classes of patterns are easily distinguished in O(m) time.

Original languageEnglish (US)
Pages (from-to)1761-1782
Number of pages22
JournalSIAM Journal on Computing
Volume31
Issue number6
DOIs
StatePublished - Sep 2002

Keywords

  • Algorithms
  • Edit distance
  • String matching

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Approximate string matching: A simpler faster algorithm'. Together they form a unique fingerprint.

Cite this