I was reading substring hash from this link. But I got confused in the bold lines below. Could anyone explain me with example?
Suppose we are given a string S, and given indices I and J. It is required to find the hash from the substring S [I..J].
By definition, we have:
H [I..J] = S [I] + S [I + 1] * P + S [I + 2] * P ^ 2 + ... + S [J] * P ^ (J-I)
H [I..J] * P [I] = S [I] * P [I] + ... + S [J] * P [J], H [I..J] * P [I] = H [0..J] - H [0..I-1]
The only problem that arises is what you need to be able to divide by
P [I]. In fact, it is not so simple. Since we compute the hash modulo 2 ^ 64, for division by
P [I] we must find the inverse element to it in the field (for example, using the Euclidean Advanced Algorithm ), and multiply by this inverse element.
However, there is an easier way. In most cases, instead of dividing hashes by degrees P, you can, conversely, multiply them by these degrees.
Suppose you have two hashes: one multiplied by
P [I], and the other by
I <J, then multiply the first hash by
P[J-I], otherwise, multiply the second hash by
P [I-J]. Now we have brought hashes to one degree, and we can safely compare them.