Approximate string matching: A simpler faster algorithm

Richard Cole, Ramesh Hariharan

Research output: Contribution to conferencePaperpeer-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 mostly periodic strings (defined later). The second algorithm runs in time O(nk4/m+n+m) on mostly periodic patterns. The two classes of patterns are easily distinguished in O(m) time.

Original languageEnglish (US)
Pages463-472
Number of pages10
StatePublished - 1998
EventProceedings of the 1998 9th Annual ACM SIAM Symposium on Discrete Algorithms - San Francisco, CA, USA
Duration: Jan 25 1998Jan 27 1998

Other

OtherProceedings of the 1998 9th Annual ACM SIAM Symposium on Discrete Algorithms
CitySan Francisco, CA, USA
Period1/25/981/27/98

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

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

Cite this