Theory Comput Syst (2012) 50:492–515 DOI 10.1007/s00224-011-9322-y Faster Approximate String Matching for Short Patterns

Abstract We study the classical approximate string matching problem, that is, given strings P and Q and an error threshold k, find all ending positions of substrings of Q whose edit distance to P is at most k. Let P and Q have lengths m and n, respectively. On a standard unit-cost word RAM with word size w ≥ logn we present an algorithm using time O nk · min log2 m logn log2 m log