Rabin-Karp

Slide a rolling hash window across the text. Each position costs O(1) to hash — compare hashes first, then verify on a match.

Time: O(n + m) avgSpace: O(1)Rolling Hash

Text

Pattern

Pattern Hash

hash("ABCD")

Window Hash

—

hash("ABCD")

text

FastSlowStep 1 / 0

Question 1/3

What is the purpose of the 'rolling hash' in Rabin-Karp?

Phaseinit

Window start0

Window"ABCD"

Matches found0

Current window

Hash match — verifying

Match confirmed

Hash collision (false alarm)

DSAverse

String Algorithms

Loading String Algorithms...

Pattern Matching

text / pattern