Rabin–Karp searches for a pattern by hashing it and text windows of the same length. Comparing hashes can quickly rule out non-matches without checking every character. section 4.0
A search proceeds window by window:
- Map characters to numbers and compute hashes for the pattern and the first text window. section 4.1
- Compare each window hash with the pattern hash. When hashes match, compare the characters to rule out a collision. section 4.1
- Slide the window by removing the outgoing character’s contribution and adding the incoming character’s contribution to update its hash. section 4.1
A rolling hash avoids recalculating each window’s hash from scratch. Collisions still require character verification; frequent collisions can degrade performance to O(n × m), while rolling updates take O(1). section 4.4
From character checks to hashes
Searching for COOL in ALICEANDJOEBAKEDCOOKIES can require checking several characters before finding a mismatch. With JOE, the example maps letters to numbers and compares its hash with text-window hashes. section 4.1
Figure 4.5 Rolling hash working with an improved hash function. The new value of the hash is obtained by subtracting the previous hash value with the character exiting the window multiplied by 10 and adding the new character. Calculation of the new hash is performed with efficiency.
The figure shows how a rolling hash updates as a window slides. section 4.1
