Rabin-Karp Visualizer

Watch Rabin-Karp compare rolling hashes and verify candidate matches with animated windows, controls, and collision explanations.

Current status: Ready. Use the controls to begin exploring Rabin-Karp.

Rabin-Karp Algorithm Visualizer

A
B
C
C
D
D
A
E
F
G
A
B
C
A
B
C
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
A
B
C

Window [0, 2]: hash 59 vs pattern hash 59.

Pattern Hash: 59
Window Hash: 59
Step 1 / 39

Animation Legend

Current Window
Verifying Character
Spurious Hit (hash collision)
Confirmed Match

Rabin-Karp computes a hash for the pattern and for each window of the text. Most windows are rejected instantly because their hash doesn't match. When hashes do match, the algorithm falls back to a character-by-character check - occasionally that check fails anyway (Yellow → Red), which is called a spurious hit.

Java Implementation

public List<Integer> rabinKarp(String text, String pattern) {
    int n = text.length(), m = pattern.length();
    int base = 256, mod = 101;
    List<Integer> matches = new ArrayList<>();

    long patternHash = 0, windowHash = 0, h = 1;
    for (int i = 0; i < m - 1; i++) h = (h * base) % mod;

    for (int i = 0; i < m; i++) {
        patternHash = (base * patternHash + pattern.charAt(i)) % mod;
        windowHash = (base * windowHash + text.charAt(i)) % mod;
    }

    for (int i = 0; i <= n - m; i++) {
        if (patternHash == windowHash && text.regionMatches(i, pattern, 0, m)) {
            matches.add(i);
        }
        if (i < n - m) {
            windowHash = (base * (windowHash - text.charAt(i) * h) + text.charAt(i + m)) % mod;
            if (windowHash < 0) windowHash += mod;
        }
    }
    return matches;
}
Average Time Complexity: O(n + m)
Worst Case: O(n * m)

What is the Rabin-Karp Algorithm?

Rabin-Karp searches for a pattern inside a text by comparing hash values instead of raw characters. It computes a hash for the pattern once, then slides a same-sized window across the text, updating the window's hash in constant time using a "rolling hash" - dropping the outgoing character's contribution and adding the incoming one.

Because different strings can occasionally share the same hash (a collision), a hash match only means "probably equal" - the algorithm always double-checks with a direct character comparison before reporting a real match. This trade-off makes Rabin-Karp especially well suited to searching for multiple patterns at once, unlike KMP or Boyer-Moore, which are tuned for a single pattern.

Time & Space Complexity

  • Average CaseO(n + m)
  • Worst CaseO(n · m)
  • SpaceO(1)

* Worst case occurs when many spurious hits force repeated full comparisons - a large modulus makes this rare in practice.

Real-World Use Cases

  • ✓
    Plagiarism DetectionHashing overlapping chunks of text to find duplicated passages quickly.
  • ✓
    Multiple Pattern SearchSearching for many patterns at once by hashing them into a set.
  • ✓
    DNA Sequence SearchLocating short subsequences within long genomic strings.

Concept guide

Review the mental model, tradeoffs, and practical use cases after you experiment.

Rabin-Karp Algorithm Complete Info Card

String MatchingHashing

Rabin-Karp slides a rolling hash across the text, rejecting most positions instantly and only falling back to a full character check when hashes happen to match.

Algorithm Characteristics

Average Time Complexity

Most windows are rejected by a single hash comparison

O(n + m)

Worst Case Time

Many spurious hits force repeated full comparisons

O(n · m)

Space Complexity

Only a rolling hash and a few counters are stored

O(1)

Core Technique

Update the window hash in O(1) instead of recomputing it

Rolling Hash

Multi-Pattern Friendly

Hashing generalizes well to searching many patterns at once

Yes

False Positives

Hash collisions require a character-by-character verification

Possible

Algorithm Steps

1

Compute the pattern's hash once

2

Compute the hash of the first text window

3

Compare the window hash to the pattern hash

4

On a hash match, verify with a direct character comparison

5

Roll the hash forward by one position in O(1)

6

Repeat until every window has been checked

When to Use

  • •Searching for multiple patterns simultaneously
  • •Plagiarism or duplicate-chunk detection
  • •Teaching hashing as a search optimization technique

When to Avoid

  • •Guaranteed worst-case linear time is required (use KMP)
  • •Small alphabets with highly repetitive text (more collisions)
  • •A poorly chosen modulus that causes frequent spurious hits
Did You Know? Rabin-Karp is named after its inventors, Richard M. Karp and Michael O. Rabin, who introduced it in 1987 specifically to make multi-pattern search practical.
Rolling hashPlagiarism detectionMulti-pattern search