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...
Credit to Drew Binsky for footage of Afghan Hash: • How Afghanistan Gets High (They Grow Their...
Written and narrated by Andre Violentyev