Consider a further generalization of the pattern matching problem from the previous exercise, where we allow the pattern, P, to contain instances of a special “wild card” or “don’t care” symbol, *, which matches any character in the alphabet, Σ. For example, with 

P = ab**c 

and 

T = babdfcabghci, 

P matches T in positions 2 and 7. Show that, even in this case, you can still find all occurrences of P in T using two calls to the Conv method. In this case, your algorithm should run in O(n log |Σ|) time, plus the time needed for the calls to the Conv method.

Data From Previous Exercise

Suppose you have a software method, Conv, that can perform the convolution of two length-n integer vectors, A and B, using the FFT algorithm described in this chapter. Suppose further that you have been asked to build a system that can take an n-bit binary “text” string, T, and an m-bit binary “pattern” string, P, for m ≤ n, and determine all the places in T where P appears as a substring. Show that in O(n) time, plus the time needed for calls to the Conv method, you can solve this pattern matching problem by making two calls to the Conv function. Hint: Note that the kth position in the convolution of two bit strings, A and B, counts the number of 1’s that match among the first k − 1 places in A with the last k − 1 places in the reversal of B.