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