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.

Fantastic news! We've Found the answer you've been seeking!

Step by Step Answer:

Related Book For  book-img-for-question

Algorithm Design And Applications

ISBN: 9781118335918

1st Edition

Authors: Michael T. Goodrich, Roberto Tamassia

Question Posted: