Rabin-Karp algorithm

If the hash values of a pattern and a current substring are equal, the algorithm saves the index of an occurrence and moves to the next iteration.

To calculate the hash value for neighbouring substrings in $O(1)$, the algorithm uses the polynomial hash functions and their rolling hash property.

Since the polynomial hash function is not a rolling hash, the algorithm uses the linear hash function for fast calculation of the substrings' hash values.

If the hash values of a pattern and a current substring are equal, the algorithm performs a direct comparison to check that the strings are indeed equal.