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:
“... in the cities there are thousands of rolling stones like me. We are all alike; we have no ties, we know nobody, we own nothing. When one of us dies, they scarcely know where to bury him.... We have no house, no place, no people of our own. We live in the streets, in the parks, in the theatres. We sit in restaurants and concert halls and look about at the hundreds of our own kind and shudder.”
—Willa Cather (1873–1947)