New hashing exercise

[AlexisEnglebert]

Hello,

Here is a new exercise about polynomial hash.

The solution idea is to compute the hash for each row with polynomial hash for e.g the string "hello" we have

hash = (h · a⁰ + e · a¹ + l · a² + l · a³ + o · a⁴) mod m (where a is the base and m the modulo)

and then we can rotate the string by simply doing some math operation on the already hashed string so to get "ohell" we remove the o from "hello"

hash = (h · a⁰ + e · a¹ + l · a² + l · a³ ) mod m

Then we multiply the hash by the basis (a)

hash = (h · a⁰ + e · a¹ + l · a² + l · a³ ) · a = (h · a¹ + e · a² + l · a³ + l · a⁴ ) mod m

And finally we add the o at the start:

(h · a¹ + e · a² + l · a³ + l · a⁴ ) + o · a⁰ = ( o· a⁰ + h · a¹ + e · a² + l · a³ + l · a⁴ ) mod m

And now we have the hash for "ohell" in O(1).