Rabin-Karp String Matching
mediumTime: O(n + m)Space: O(1)
Signals to notice
pattern matching via rolling hashO(1) window hash updateverify on match
Brute force first
Compare every window — O(nm).
The key insight
Rolling hash: update hash in O(1) per slide. Compare characters only on hash match. Average O(n+m).
What must stay true
Rolling hash detects potential matches in O(1). Character comparison verifies (handles collisions).
Easy way to go wrong
Not verifying hash matches — collisions give false positives.