1. A certain hash function for a string of characters C-cm- is given by: 5% x 31(m-i-1) -Po 31m-1 + C1 31m-2 + + cm-1 31lmod 232 (a) Suppose we want to find the first occurrence of a string P-PoPPk-1 in a string Q- mod 232 og19N-1, where N>>k. We can first find the hash code for P and then compare it with hash codes of k-length substrings of Q: Q gok-1, Q-.k, etc. until the hash codes match, or no further k-length substrings of Q are left. If a match occurs then P must be compared character by character to the substring of Q for which the hash codes match. If no match of hash codes is found, no substring of Qis equal to P From equation (1) above, show that, if the hash code for Q is known, the hash code for Q+1 can be found in constant time. (b) Give the runtime of the string matching algorithm in "big O notation in terms of N and k One of the best algorithms (Boyer-Moore) takes O(N) time and, if there is no match, takes N/M time.] 1. A certain hash function for a string of characters C-cm- is given by: 5% x 31(m-i-1) -Po 31m-1 + C1 31m-2 + + cm-1 31lmod 232 (a) Suppose we want to find the first occurrence of a string P-PoPPk-1 in a string Q- mod 232 og19N-1, where N>>k. We can first find the hash code for P and then compare it with hash codes of k-length substrings of Q: Q gok-1, Q-.k, etc. until the hash codes match, or no further k-length substrings of Q are left. If a match occurs then P must be compared character by character to the substring of Q for which the hash codes match. If no match of hash codes is found, no substring of Qis equal to P From equation (1) above, show that, if the hash code for Q is known, the hash code for Q+1 can be found in constant time. (b) Give the runtime of the string matching algorithm in "big O notation in terms of N and k One of the best algorithms (Boyer-Moore) takes O(N) time and, if there is no match, takes N/M time.]