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.
2 Answers 2
What you are missing is the identity $$ (a + b) \bmod{Q} = (a \bmod{Q} + b \bmod{Q}) \bmod{Q}. $$
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.