After spending O(n) time on preprocessing h, we have an efficient way to compute the hash code for any subsequence of S.

The division operation modulo a prime needs some number theory insight. You can do it using Fermat's little theorem or using the Extended Euclidean Algorithm. If you need to process a lot of sub strings it may be useful to pre process all the values for <tex>a^{-i} modulo p</tex>.

The division operation modulo a prime needs some number theory insight. You can do it using Fermat's little theorem or using the Extended Euclidean Algorithm. If you need to process a lot of sub strings it may be useful to pre process all the values for <tex>a^{-i} mod p</tex>.

h2. Caveats