liveBook · Manning

Rabin-Karp algorithm

As explained in Algorithms Every Programmer Should Know

The Rabin-Karp algorithm is a string-search procedure that compares hash values of a pattern and text windows before verifying character matches.

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

How Algorithms Every Programmer Should Know covers it

How deep it goes
Works through hashing, rolling updates, collision checks, pseudocode, and complexity, then points to production scaling.
Examples
Traces COOL and JOE searches, character-to-number mappings, and plagiarism checks on documents and biological sequences.
What it assumes
Builds from basic character-to-number mappings and hashing, without assuming prior understanding of hashing.
What you can do after
Apply it with a Python implementation that returns the starting indices of pattern matches.
How it connects
Connects string matching with hashing, rolling hash, sliding windows, plagiarism detection, and bioinformatics.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.