1
$\begingroup$

My question was around the rolling hash function in RobinKarp algorithm. It is intuitive for me to understand how to get from xi to xi+1 without the mod, however with the mod i am not sure how we still get the right answer. Is there any mathematical theroem anyone could quote which would help me understand?

So i get,

xi = (ti)R^0 + (ti+1)R^1 + .. + (ti+m-1)R^M-1
xi+1 = (xi - (ti)R^0)/R + (ti+m)R^M

but whats the guarantee,

xi = [ (ti)R^0 + (ti+1)R^1 + .. + (ti+m-1)R^M-1 ] mod Q
xi+1 = [ (xi - (ti)R^0)/R + (ti+m)R^M ] mod Q

.. and so on will be correct even after introducing mod Q

Pretty sure its some basic mod arithmetic theorem i am missing here.

$\endgroup$
1
$\begingroup$

What you are missing is the identity $$ (a + b) \bmod{Q} = (a \bmod{Q} + b \bmod{Q}) \bmod{Q}. $$

$\endgroup$
2
$\begingroup$

The video actually does it the other way around, kicking out the term with the highest power and then multiplying by R. It turns out to not really make a difference, but this is clearly always possible regardless of whether modular arithmetic is used or not.

Going back to what you wrote though. Without the modular arithmetic, the division by R is possible because the dividend is a multiple of R (it was carefully constructed to be).

With the modular arithmetic, the division by R is possible because R and Q are chosen such that $\gcd(R, Q) = 1$, therefore R has a modular multiplicative inverse modulo Q and can always be divided by. As a bonus, dividing by R becomes a multiplication, which is easier than integer division even if it is by a constant.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.