1. A certain hash function for a string of characters CCocCm-1 is given by: hash(C) mod 232 (a) Suppose we want to find the first occurrence of a string P Pop .Pk-1 in a string Q oi IN-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: Qgogk-1, Q11g2 .qk, 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 Q is equal to P From the above equation, show that, if the hash code for Q is known, the hash code for Qi+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 CCocCm-1 is given by: hash(C) mod 232 (a) Suppose we want to find the first occurrence of a string P Pop .Pk-1 in a string Q oi IN-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: Qgogk-1, Q11g2 .qk, 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 Q is equal to P From the above equation, show that, if the hash code for Q is known, the hash code for Qi+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.]