RavensMove

Rabin Karp Visualizer

Enter text and a pattern, tune the rolling hash, then step through hash checks, collisions, and verified matches.

Windows
0
Matches
0
Window Hash
56
Pattern Hash
88

String input

Step controls

Start Rabin-Karp with pattern hash 88 and first window hash 56.

Rolling window

0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
A
B
A
B
D
A
B
A
C
D
A
B
A
B
C
A
B
A
B
A
B
A
B
C
A
B
A
B

Window hashes

ShiftWindowHashStatus
0ABABDABAC56start
1BABDABACD17pending
2ABDABACDA5pending
3BDABACDAB89pending
4DABACDABA55pending
5ABACDABAB91pending
6BACDABABC88pending
7ACDABABCA1pending
8CDABABCAB75pending
9DABABCABA83pending
10ABABCABAB88pending

Hash output

shift = 0
pattern_hash = 88
window_hash = 56
matches = []
checked_windows = 0
verifications = 0
base = 256
modulus = 101
No matches found yet.

What is a Rabin Karp Visualizer?

A Rabin Karp visualizer shows how rolling hashes can find candidate pattern matches inside a text string. Instead of comparing every character at every shift first, Rabin-Karp compares a pattern hash with the current window hash, then verifies characters when the hashes match.

This tool lets you enter text and a pattern, adjust the hash base and modulus, then step through hash checks, rolling updates, possible collisions, and confirmed match indexes.

For the full algorithm set, browse the Data Structure Visualizers hub.

How to use this Rabin Karp visualizer

  • Enter the text to scan.
  • Enter the pattern to search for.
  • Adjust the base and modulus if you want a different rolling hash.
  • Click Run Rabin Karp to jump to the completed match list.
  • Step forward to watch the current window hash, pattern hash, rolling update, and match verification.

Rabin-Karp vs KMP

Rabin-Karp uses hashing to filter candidate windows. KMP uses the LPS table to avoid moving the text pointer backward after a mismatch. Both are useful string matching algorithms, but they explain different ideas.

Compare this page with the KMP String Matching Visualizer and Z Algorithm Visualizer to see prefix-based matching without rolling hashes.

Frequently Asked Questions

What does Rabin-Karp use a rolling hash for?
The rolling hash lets the algorithm update the current text window hash in O(1) time when the window shifts by one character.
Why does Rabin-Karp verify characters after a hash match?
Different strings can share the same hash value, so the algorithm confirms each candidate match with a direct character comparison.
What is a hash collision in Rabin-Karp?
A collision happens when the pattern hash equals a window hash but the actual characters are different.
What is the average time complexity of Rabin-Karp?
With a good hash, Rabin-Karp runs in O(n + m) average time for one pattern, where n is the text length and m is the pattern length.

Related tools

Binary Search Tree VisualizerBinary Search VisualizerPrefix Sum Visualizer