bq. Given a string P of length n and a string S of length m find out all the occurrences of P within S

The algorithm works by building a fingerprint for each subsequence of S of length n. It checks if any of them match the fingerprint of P. Implementing this directly leads to a $O(n*m)$ solution which isn't faster than the naive matching algorithm (in fact it might be even slower).

The algorithm works by building a fingerprint for each subsequence of S of length n. It checks if any of them match the fingerprint of P. Implementing this directly leads to a $O(n*m)$ solution which isn't faster than the naive matching algorithm (in fact it may be slower).

*The insight* is that you can efficiently compute the hash value of a subsequence using the hash value of previous subsequence if you use the right hash function. A polynomial with the string characters as coefficients works well. Let <tex>H(c)=c[0]a^{n-1} + c[1]a^{n-2}+...+c[n-1]</tex> be the hash function for the string c.
All the operations are done modulo a prime number so that we don’t have to deal with large integers.