Suppose we want to find the first occurrence of a string P1P2 Pk in a long inputstring

Chapter 5, Problem 5.15

(choose chapter or problem)

Suppose we want to find the first occurrence of a string P1P2 Pk in a long inputstring A1A2 AN. We can solve this problem by hashing the pattern string, obtaininga hash value HP, and comparing this value with the hash value formed fromA1A2 Ak, A2A3 Ak+1, A3A4 Ak+2, and so on until ANk+1ANk+2 AN.If we have a match of hash values, we compare the strings character by characterto verify the match. We return the position (in A) if the strings actually do match,and we continue in the unlikely event that the match is false.a. Show that if the hash value of AiAi+1 Ai+k1 is known, then the hash valueof Ai+1Ai+2 Ai+k can be computed in constant time.b. Show that the running time is O(k + N) plus the time spent refuting falsematches. c. Show that the expected number of false matches is negligible.d. Write a program to implement this algorithm.e. Describe an algorithm that runs in O(k + N) worst-case time. f. Describe an algorithm that runs in O(N/k) average time.