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:
“He says the waves in the ship’s wake
are like stones rolling away.
I don’t see it that way.”
—Denise Levertov (b. 1923)