Sign in to watch this lesson
Algorithms - Strings · 4:38
Rabin-Karp and Hash with Binary Search
Rabin-Karp finds a pattern by sliding a window along the text and comparing one number per position: the window's prefix-hash difference against the pattern's hash times p^i, for O(|s| + |t|) in total. We watch a fake hit appear with a toy modulus and get caught by checking the letters, then use binary search on the length, with one hashing sweep per probe, to find the longest repeated substring.
You will learn
- Compare every length-|s| window of a text with a pattern in O(1) each using prefix hashes: (h[i+S] - h[i]) mod m == hash(s) * p^i mod m
- Explain why equal hashes only mean 'probably equal', and handle fake hits by checking the letters or by double hashing
- Recognise a monotone yes/no question on a length and solve it with binary search plus one hashing sweep per probe (longest repeated or common substring)
- Avoid the classic slips: a power table too short for the text, dividing instead of multiplying, and single hashing across many probes