Rabin-Karp Rolling Hash
The Rabin-Karp string search algorithm is normally used with a very simple rolling hash function that only uses multiplications and additions:
where is a constant and are the input characters.
In order to avoid manipulating huge values, all math is done modulo . The choice of and is critical to get good hashing; see linear congruential generator for more discussion.
Removing and adding chars simply involves adding or subtracting the first or last term. Shifting all chars by one position to the left requires multiplying the entire sum by . Shifting all chars by one position to the right requires dividing the entire sum by . Note that in modulo arithmetic, can be chosen to have a multiplicative inverse by which can be multiplied to get the result of the division without actually performing a division.
Read more about this topic: Rolling Hash
Famous quotes containing the word rolling:
“The gods had condemned Sisyphus to ceaselessly rolling a rock to the top of a mountain, whence the stone would fall back of its own weight. They had thought with some reason that there is no more dreadful punishment than futile and hopeless labor.”
—Albert Camus (1913–1960)