Article ID Journal Published Year Pages File Type
428062 Information Processing Letters 2008 6 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics