Bit-parallel string matching under Hamming distance in O(n⌈m/w⌉) worst case time

Given two strings, a pattern P of length m and a text T of length n over some alphabet Σ, 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⌈mlog(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 O(n⌈mloglog(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.