I m learning Hashing from HERE , Now in this the topic “hash value of a substring”
hash(s[i..j]) = ( (hashvalue upto j - hasvalue upto i-1 ) / p^i ) mod m
hash(s[i..j]) = ( (hashvalue upto j - hasvalue upto i-1 ) * inversemod(p^i ) ) mod m
I m calcultaing prefix hashvalue (not suffix as many git repo use suffix (i m confusing in suffix so) ) Now I can easily calculate inversemod(p^i) by first calculating x = p^i mod m and then x^(m-2) mod m … fo for each power i it takes n(logn*logn) time , so how can precompute inverse of every p^i lesser than this time ?
In the above code. He is multiplying with power which is pre calculated. The reason here is, consider you have p^6+p^7+p^8 and p^2+p^3+p^4, Here we are using rolling hash, so we need to subtract r and l-1 right?. As p is raised to some power we cant directly subtract instead we raise both of them to equal powers, Now if we multiply p^2+p^3+p^4 with p^4 It becomes p^6+p^7+p^8, We have equal powers and can be subtracted and As we are calculating mod, hash[r] might be less than hash[l-1] so subtract with mod.Same with sufix also. prefix implementation