Suppose you have a software method, Conv, that can perform the convolution of two length-n integer vectors,
Question:
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.
Step by Step Answer:
Algorithm Design And Applications
ISBN: 9781118335918
1st Edition
Authors: Michael T. Goodrich, Roberto Tamassia