Bit-parallel string matching under Hamming distance in O(n[m/w]) worst case time
Given two strings, a pattern P of length in and a text T of length n over some alphabet Sigma, we consider the string matching problem under k mismatches. The well-known Shift-Add algorithm [R.A. Baeza-Yates, G.H. Gonnet, A new approach to text searching, Comm. ACM 35 (10) (1992) 74-82] solves the problem in O(n[m log(k)/w]) worst case time, where w is the number of bits in a computer word. We present two algorithms that improve this result to 0(n fin log log(k)/w]) and O(n[m/w]), respectively. The algorithms make use of nested varying length bit-strings, that represent the search state. We call these Matryoshka counters. The techniques we developed are of more general use for string matching problems. (c) 2007 Elsevier B.V. All rights reserved.
bit-parallelism hamming distance algorithms approximate string matching