Unable to understand the hash function of Rabin Karp Algorithm explained at topcoder -
i reading rabin karp algorithm @ topcoder. in that article, not able following hash evaluation.
// calculate hash value of first segment // of text of length m ht = 0; for(i = 0; < m; i++) ht = int_mod(ht * b + text[i], m);
it looks different explained in theory. know free use hash function in rabin karp, still maintain flow of tutorial, need explaination possibly not understanding correctly.
to me looks same in theory before. trick in small steps (constructing polynomial)
consider simple example of string of length 3:
we initialize ht = 0
. loop first position 0: ht = text[0]
now, position 1 first power of b
: ht = text[0]*b + text[1]
. in third iteration second power multiplying b
whole 'polynomial' again: ht = text[0]*b^2 + text[1]*b + text[2]
. , of course can modulo m
@ every step.
this hash above in article.
Comments
Post a Comment