8 a) The brute-force pattern matching algorithm on the slides runs until either a. A match is found, or b. All placements of the pattern have been tried Write the pseudocode for an algorithm such that it reports all occurrences of a pattern P with the number of shifts needed to achieve that.

b) Show the comparisons the naive string matcher makes for the pattern P = 0001 in the text T = 000010001010001

c) Suppose that all characters in the pattern P are different. Show the pseudocode of an algorithm that accelerate the brute-force algorithm to run in time O(n) on an n-character text T.

d) Using Boyer-Moore's algorithm and the text "puppy puppet looks happy", find the substring puppet. Compute first the last occurrence function. For the alphabet assume it is the letters that compose the text. Discard blank spaces.

e) Following the Boyer-Moore algorithm, what is the number of comparisons required for finding the the previous pattern in the given text? Help yourself with a drawing similar to the examples showed in class and paste it with your answer.