Question

Use Boyer-Moore's algorithm to find the substring “puppet” in the text "puppy puppet looks happy".

(a). First compute the last occurrence function. For the alphabet assume it is the letters that compose the text. Ignore blank spaces.

(b). Following the Boyer-Moore algorithm, what is the number of comparisons required for finding the pattern in the given text? Include a trace of the algorithm execution, similar to those shown in class, positioning puppet beneath the beginning of the text and then at all its subsequent positions until found in the text.

Answer 1