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.
Best How To :
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:
ht = 0. The loop will first get position 0:
ht = text Now, for position 1 we get the first power of
ht = text*B + text. In the third iteration we get the second power by multiplying
B to the whole 'polynomial' again:
ht = text*B^2 + text*B + text. And of course we can do it modulo
M at every step.
This is exactly the hash from above in the article.