Cormen String matching Rabin-Karp

Question

I am reading Rabin-Karp algorithm by Introduction to Algorithms by Cormen etc.

www.cs.uml.edu/~kdaniels/courses/ALG_503_F08/503_lecture11.ppt

Note here == is used as mod operator

Above notes on slide 13 i.e., Eq 34.2, which is attached as picture here. In equation we have h == (d)powerof((m-1) (mod q) is value of digit "1" in the high order position of an m-digit text window.

My question here what does author mean by "value of digit "1" in the high order position of an m-digit text window" ?

On slide 14 how author got (7-3.3).10 + 2 (mod 13) as 8 (mod 13)?

In Average case analysis it is mentioned that we can base a heuristic analysis on the assumption that reducing values modulo q acts like a random mapping from sigma* to Z. Here what does author mean by above statement?

Answer 1

Your second question seems just to be about modular arithmetic with -ve numbers. One way to think of this is that working mod M you are free to add or subtract M as much as you like, since M is equivalent to 0 mod M. So we have (7-3.3).10 + 2 (mod 13) = -2.10 + 2 = -18 = 13 + 13 - 18 = 8 mod 13

Your first question is less clear to me, but let me work through it in detail. When a character first appears in the text window, it is just added in. Then it shifts along the text window, and finally we want to remove all memory of it, so that after it moves out of the text window it does not affect the hash value.

At first we see character x, and add it to the hash value so far, so we get h.d + x. When we see the next character we multiply that by d (and do the other stuff I am trying to explain) and then add on the new character - say y. So we get ... + x*d + y. The next step gives us ... + x*d*d + y*d + z. When we are just about to get rid of the character we have a hash value of x*d^(m-1) + ...., where .... depends only on characters after x. So we can remove the influence of x on the hash value by subtracting x*d^(m-1) before multiplying by d.