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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

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

Improve this answer
$\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.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.