Robert West

Sublinear Approximate String Matching

Abstract

The present paper deals with the subject of approximate string matching and demonstrates how Chang and Lawler conceived a new sublinear time algorithm out of ideas that had previously been known.
The problem is to find all locations in a text of length n over a b-letter alphabet where a pattern of length m occurs with up to k differences (substitutions, insertions, deletions).
The algorithm will run in O(n/m k log m) time when the text is random and k is bounded by the threshold m/(log m + O(1)). In particular, when k=o(m/ log m) the expected running time is o(n).