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 related pattern-matching and string dynamic-programming tools, browse the String Algorithm 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