# Approximate string matching: a simpler faster algorithm

Cole, Richard ; Hariharan, Ramesh (2002) Approximate string matching: a simpler faster algorithm SIAM Journal on Computing, 31 (6). pp. 1761-1782. ISSN 0097-5397

Full text not available from this repository.

Related URL: http://dx.doi.org/10.1137/S0097539700370527

## 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(\frac{nk^3}{m}+n+m)$ on all patterns except k-break periodic strings (defined later). The second algorithm runs in time $O(\frac{nk^4}{m}+n+m)$ on k-break periodic patterns. The two classes of patterns are easily distinguished in O(m) time.

Item Type: Article Copyright of this article belongs to Society for Industrial and Applied Mathematics. 102328 09 Mar 2018 11:27 09 Mar 2018 11:27

Repository Staff Only: item control page