2008/11/21 by Philip Bille, Bille, Philip
Computer Science · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Network Packet Processing and Optimization #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.0811.3490
openalex publication_date 2008/11/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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((log2 m)/(log n),(log2 mlog w)/(w)) + n) When P is short, namely, m = 2o(√(log n)) or m = 2o(√(w/log w)) 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.