Medium · Rabin-Karp Rolling Hash
Understand → Visualise → Practice.
Return the first pattern occurrence using a rolling hash and verify hash matches to avoid collisions.
Treat each window as a number in base B modulo a large prime. Sliding the window removes the leading character's contribution and adds the new one, so each step is O(1).
h = h × B + code (mod p) over each character.
Remove the old first character (subtract code × B^(m−1)), multiply by B, add the new character.
When the hashes are equal, compare the actual substring to rule out a collision.
O(n + m) expected time and O(1) extra space.
Trusting equal hashes without comparing the text can report false matches.
Read the full guide first: Strings: Frequencies, Matching and Palindromes.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.