Faster Approximate String Matching for Short Patterns

摘要

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 > log n we present an algorithm using time O(nk·min((log~2m)/(log n),(log~2m log w)/w)+n) When P is short, namely, m = 2~(0((log n)~(1/2)) or m = 2~(0((w/log w)~(1/2)) this improves the previously best known time bounds for the problem. The result is achieved using a novel implementation of the Landau-Vishkin algorithm based on tabulation and word-level parallelism.