We saw a neat way to recover hashes using rolling hash, but unfortunately, we still ended up with a hashing collision in the case of palindromic strings. Simply multiplying primes will not make a good hash function. For this reason, the Rabin-Karp algorithm uses a Polynomial Hash Function. This is a combination of sums and products (as opposed to only products) to make the final output more unique and therefore almost entirely immune to hash values colliding.
In Python, a polynomial hash of a string 'ABCD' can be calculated as follows:
In this exercise, we will implement the same idea but automate the process using for loops.
Instructions
Complete the function polynomial_hash() to return the polynomial hash of a generic substring s of uppercase. Using the example above as a reference that showed you how to calculate the polynomial hash of 'ABCD', think about how you would do this for any generic substring.
Use a for loop to iterate through all character indexes in s. Then sum up the individual contributions of each character towards the total polynomial hash of s.
The contribution of each character is its ASCII value multiplied by some power of 26. The exponent of 26 starts at len(s)-1 for the first character and goes down by 1 for each subsequent character.
Use string slicing and a for loop to access all the substrings of length 4 in uppercase. Find the polynomial hash of each of these substrings using the polynomial_hash() function you have just implemented.
Store the mapping of each substring of length 4 to its corresponding polynomial hash in the polynomial_hash_values dictionary.