Efficient pattern-matching with don't cares
Adam Tauman Kalai · 2002
Abstract We present a randomized algorithm for the string matching with don't cares problem. Based on the simple fingerprint method of Karp and Rabin for ordinary string matching [4], our algorithm runs in time O(n log m) for a text of length n and a pattern of length m and is simpler and slightly faster than the previous algorithms [3, 5, 1]. 1 Introduction. We extend the simple randomized fingerprinting algorithm of Karp and Rabin [4] to the problem of string matching with don't cares. Our algorithm uses a single, simple convolution. This is optimal in the sense that the string matching with don't cares problem is at least as hard as the boolean convolution problem [6]. Thus, to improve our run time of O(n log m) on text of length n and pattern of length m, one would have to improve on the Fast Fourier Transform.