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.