Pular para o conteúdo principal
Interactive Algorithm Education

Visualize & Master Algorithms & Data Structures

Explore classic & modern sorting algorithms, efficient searching techniques, and interactive data structure visualizations — all with real-time step-by-step animation, comparisons, swaps, and Big-O metrics.

String Matching Visualizer

Rabin-Karp

Passo 0 / 0
Speed 100ms
Step Progress 0 / 0
Comparisons 0
Matches Found 0
Status Ready
Text / Pattern
Comparing
Matched
Window / Aux highlight
Match found
Step Explanation

Select an algorithm and press Play to watch the pattern slide across the text.

—
Pseudocode 
 
 
 
 
  
 
 
Rabin-Karp
  
 
  Elementary (2/5)
 
~45 minutes   Rolling hash  Hash-and-verify  Collision handling  Multi-pattern search  
Prereqs: String basics, Modular arithmetic (mod, base)  
 
Quick Reference
Rabin-Karp
Rabin-Karp hashes the pattern and every length-m window of the text using a rolling hash, comparing hashes first. Only when a hash collision occurs does it verify the actual characters, so most windows are skipped in constant time.

Difficulty: Elementary (2/5)
string
Complexity
Best Time
O(n + m)
Average Time
O(n + m)
Worst Time
O(n·m)
Space
O(1)
When to Use
Use Rabin-Karp when you need to search for multiple patterns at once (each window hash can be compared against many pattern hashes), or when the text is dominated by rare hash collisions.
Pros
  • Rolling hash slides in O(1) per window
  • Extends naturally to multi-pattern search
  • Constant extra space
Cons
  • Worst case O(n·m) with many collisions
  • Hash collision requires character verification
  • Choosing the base and modulus matters
History
Rabin-Karp was published in 1987 by Michael Rabin and Richard Karp. Its rolling-hash idea came directly out of the randomized-hashing work in string matching, and it is the basis of substring-hash tricks used in competitive programming.
 
 
Pattern matching, hashed. Instead of comparing characters, Rabin-Karp computes a hash of the pattern and a hash of every equal-length window of the text — then compares numbers instead of letters. A good hash rejects almost every window instantly, and a trick called the rolling hash recomputes each window in O(1).


How It Works


    

  1. Hash the pattern: hash(s) = (c₁·bᵐ + c₂·bᵐ⁻¹ + ... + cₘ) mod p, using a base b and prime p.
    2. 

  2. Roll the window: slide one character at a time; each new hash derives from the previous in O(1):

    h(win+1) = ((h(win) − T[win]·b^(m−1)) · b + T[win+m]) mod p
    

    3. 

  3. Compare hashes: equal hashes mean a probable match — verify the actual characters to rule out collisions.
    4. 

  4. Record confirmed matches.
    5. 



Key Insight


The rolling hash makes every slide cheap: subtract the outgoing leftmost character’s contribution, shift everything left by one, and add the new character. So the whole scan is O(n) if collisions are rare — and a well-chosen prime keeps them rare. That’s why the average case is O(n + m) but the worst case O(n·m) (e.g., when a pathological pattern hashes equal to nearly every window).


Worked Example


The visualizer searches for pattern P = 31415 in the digit text T = 2359023141526739921.


The pattern’s hash is computed once. The window slides left to right; most windows hash to something different and are rejected with a single integer comparison — no character work. The window starting at text position 6 hashes equal to the pattern, so the algorithm verifies character-by-character: 3 1 4 1 5 all agree, and the match at position 6 is reported. Total work stays near-linear because only that one window survived the hash filter.


Edge Cases & Pitfalls


    

  • Collisions are real: equal hashes can occur without a match — always verify characters before reporting.
    • 

  • Modulo arithmetic negatives: (a − b) mod p can go negative; add p before reducing.
    • 

  • Base choice: using a base larger than the alphabet (e.g. 256 for ASCII) reduces collisions.
    • 

  • Prime choice: a large prime reduces collisions; a small one makes them likely.
    • 

  • Worst case: adversarial inputs can force a verify on every window → O(n·m).
    • 



Comparison: Rabin-Karp vs KMP vs Naive





































AspectNaiveKMPRabin-Karp
AverageO(n·m)O(n + m)O(n + m)
WorstO(n·m)O(n + m)O(n·m)
SpaceO(1)O(m)O(1)
Multi-patternNoNoYes


Applications


    

  • Plagiarism detection — compare many document windows against many patterns
    • 

  • Multi-pattern search — check one window hash against a set of pattern hashes
    • 

  • Duplicate detection — rolling hashes power dedup and similarity tools
    • 



Practice Trajectory


    

  1. Compute the pattern hash for 31415 with a small base by hand.
    2. 

  2. Roll the hash from the first window to the second and verify the O(1) update.
    3. 

  3. Watch the visualizer reject the non-matching windows on hash alone.
    4. 

  4. Construct a case where two strings collide under a small modulus.
    5. 

  5. Extend to two patterns and verify both are found in one text pass.
    6.