Rabin-Karp String Matching
mediumTime: O(n + m)Space: O(1)
Recognize the pattern
pattern matching via rolling hashO(1) window hash updateverify on match
Brute force idea
Compare every window — O(nm).
Better approach
Rolling hash: update hash in O(1) per slide. Compare characters only on hash match. Average O(n+m).
Key invariant
Rolling hash detects potential matches in O(1). Character comparison verifies (handles collisions).
Watch out for
Not verifying hash matches — collisions give false positives.