Rolling Hash Function Tutorial, used by Rabin-Karp String Searching Algorithm

In this tutorial we are going to discuss how to implement a "rolling hash function". We will derive a concrete implementation and show how it could be used to efficiently find a pattern string in a text. The search algorithm that makes use of it was invented by Richard M. Karp and Michael O. Rabin (1987).

The main benefit of a rolling hash function is that regardless of the length of the search pattern, we do a constant number of operations to compute the next hash value.

Making use of this property of modulo multiplication:
(A * B) mod C = ((A mod C) * (B mod C)) mod C
we show how the hash could be computed without having to deal with large numbers.

Wikipedia: https://en.wikipedia.org/wiki/Rolling_hash

Credit to Drew Binsky for footage of Afghan Hash: https://youtu.be/eHsW-xA-1Sc

Written and narrated by Andre Violentyev

Видео Rolling Hash Function Tutorial, used by Rabin-Karp String Searching Algorithm канала Stable Sort