Faangprep Logo
LoginRegister
Browse Curriculum

Rabin-Karp Algorithm

Visualize pattern searching using Rolling Hash to avoid unnecessary character comparisons.

Pattern Hash

-

Window Hash

-

Ready to search with Rabin-Karp.
A
65
B
66
C
67
C
67
D
68
D
68
A
65
E
69
F
70
G
71
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.
Unlock VisualizerPREMIUM FEATURE

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".

Stop Guessing, Start Mastering.

Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.

Start Your Premium Prep