Rolling Hash Rabin-Karp Algorithm
Slide a window of length m over text; recompute hash in O(1) per step by subtracting the outgoing character and adding the incoming one. Compare hashes first; verify character-by-character only on hash match. LC 28, 187, 1044, 2156.
Unvisited
Current window
Match confirmed
Hash collision (false positive)
Controls
Time: O(n+m) avg | Space: O(1)
Steps
0 stepsPress Run to trace the algorithm one step at a time.