Search code examples
stringalgorithmhashrabin-karp

Understanding how rolling hash works with modulus in Rabin Karp algorithm

I am having trouble understanding how the rolling hash algorithm works after the hash has been reduced to modulus value by dividing by a prime number.

Consider the sequence of 5 digits in the number 123456.

The first chunk is 12345. I store the value, in the next window, 6 comes in and 1 goes out.

So the new hash will be (12345-1*10^4)*10 + 6 = 23456. This is fairly intuitive.

As obvious, these numbers are large, so we need a modulus function to keep them small. Suppose I take 101 as the prime number for this purpose.

So 12345 will reduce to 23. How then, from this, will I derive the rolling hash for the next window, 23456?

Solution

  • You calculate it the same way you calculate 23456, but always with modulo 101.

    (((23 - (10^4 mod 101))*10) mod 101 + 6) mod 101 = 24.

    which is the value you want because 23456 mod 101 = 24.