Unable to understand the hash function of Rabin Karp Algorithm explained at topcoder

Question

I was reading the Rabin Karp Algorithm at Topcoder. But in that article, I am not able to get the following hash evaluation.

  // calculate the hash value of the first segment 
  // of the text of length m
  ht = 0;
  for(i = 0; i < m; i++) 
    ht = int_mod(ht * B + text[i], M);

It looks different from what explained in the theory. I know that I am free to use any hash function in the Rabin Karp, but still to maintain the flow of the tutorial, I need explaination as possibly I am not understanding it correctly.

Answer 1

To me it looks the same as in the theory before. The trick is that they do it in small steps (constructing the polynomial)

Consider a very simple example of a string of length 3:

We initialize ht = 0. The loop will first get position 0: ht = text[0] Now, for position 1 we get the first power of B: ht = text[0]*B + text[1]. In the third iteration we get the second power by multiplying B to the whole 'polynomial' again: ht = text[0]*B^2 + text[1]*B + text[2]. And of course we can do it modulo M at every step.

This is exactly the hash from above in the article.