if i want to find hash of the substring of string whose length is of order 10^6
then there is rule :-
hash[i…j] = ((hash[0…j]-hash[0…i-1])%m)/(p^i) // p is prime
but how can we handle division of numerator by big no like (p^(10^6)) since string is of order 10^6 it means i can be of order 10^6
What if hash[i…j] = ((hash[0…j]-hash[0…i-1])%m)/( (p^i) %m) a?
I think it will clear your doubt.
I think this article is an excellent read on this topic: String Hashing
So by knowing the hash value of each prefix of the string ss, we can compute the hash of any substring directly using this formula. The only problem that we face in calculating it is that we must be able to divide hash(s[0…j])−hash(s[0…i−1])hash(s[0…j])−hash(s[0…i−1]) by pipi. Therefore we need to find the modular multiplicative inverse of pipi and then perform multiplication with this inverse. We can precompute the inverse of every pipi, which allows computing the hash of any substring of ss in O(1)O(1) time.
However, there does exist an easier way. In most cases, rather than calculating the hashes of substring exactly, it is enough to compute the hash multiplied by some power of pp. Suppose we have two hashes of two substrings, one multiplied by pipi and the other by pjpj. If i<ji<j then we multiply the first hash by pj−ipj−i, otherwise we multiply the second hash by pi−jpi−j. By doing this, we get both the hashes multiplied by the same power of pp (which is the maximum of ii and jj) and now these hashes can be compared easily with no need for any division.