Learn

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:

``ord('A') * 26**3 + ord('B') * 26**2 + ord('C') * 26**1 + ord('D') * 26**0``

In this exercise, we will implement the same idea but automate the process using `for` loops.

### Instructions

1.

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.

2.

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.