Faangprep Logo
Log inStart free
Browse curriculum

Rabin-Karp Algorithm

The Rabin-Karp algorithm searches for a pattern in a text using a rolling hash to avoid unnecessary character comparisons.

PATTERN HASH 203

HASH

A

0

B

1

C

2

C

3

D

4

D

5

A

6

E

7

F

8

G

9

Pattern hash

203

Window hash

198

Matches found

 

Hash the pattern "CDD" once: 203. Then hash the first window "ABC": 198.

Next

Hash 198 at index 0 is not 203, so "ABC" cannot be the pattern. No characters compared.

Text

Pattern

Intuition

Comparing strings character by character is slow (O(M)). Comparing integers (hashes) is fast (O(1)). Rabin-Karp hashes the pattern and the current window. If hashes match, we double-check characters.

Concept

  • Rolling Hash: Efficiently update the hash when the window slides by removing the leading character and adding the trailing one.
  • Spurious Hit: When hashes match but strings don't (collision).
  • Complexity: Average O(N+M), Worst case O(N*M) (many collisions).

How it Works

Algorithm:

  1. Calculate hash of Pattern and first window of Text.
  2. Loop through text:
  3. If Hash(Window) == Hash(Pattern), check characters.
  4. If match, record index.
  5. Update hash for next window using Rolling Hash formula.

Step-by-Step Breakdown

Watch the visualization:

  • See the hash value update instantly as the window moves.
  • Notice that we only check characters when the hash matches (Green Box).

When to Use

  • Multiple pattern search (can check multiple hashes at once).
  • Plagiarism detection.

When NOT to Use

  • Single pattern search where KMP is safer (no collisions).

How to Identify

"Rolling hash", "Multiple patterns", "String matching".

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description
Previous

KMP Algorithm

Next

Bubble Sort

Frequently Asked Questions

What makes the hash "rolling"?

Treating the window as a number in some base lets you advance it by removing the leading character and adding the new trailing one, which is O(1) instead of rehashing all M characters.

What is a spurious hit?

A window whose hash equals the hash of the pattern while the characters differ. Hashing is lossy, so every hash match must be confirmed by comparing characters, and that is why the worst case is O(N*M).

Why choose a large prime modulus?

It spreads hash values and makes collisions rare, which keeps the average at O(N + M). A small modulus produces frequent spurious hits and forces character comparisons on most windows.