core practice · coding problem
Rabin-Karp substring search
Implement findAll(text, pattern) returning every start index where pattern occurs, using a rolling hash. You MUST verify a character-by-character match on every hash hit — a hash collision is not a match.
The mechanism
Naive matching restarts the pattern after every mismatch, throwing away what the prefix already proved. KMP precomputes how far it can safely jump using the longest proper prefix that is also a suffix, so the text pointer never moves backwards. Rabin-Karp takes the other route: hash a window, roll the hash in O(1) as it slides, and only compare characters when hashes agree — which makes it the natural choice for multi-pattern search and the reason collisions must still be checked.
Expected evidence
findAll('abababa','aba') -> [0,2,4]Try this drill in the practice workspace →
Hints when you need them
- Roll the hash by removing the leading character's contribution and appending the new one; do not rehash the window.
- On a hash hit, compare the substring. Skipping that check is the bug this drill is about.
Watch for these mistakes
- Treating a Rabin-Karp hash match as a match — you must verify the characters, or an adversarial input degrades to O(nm)
- Building the KMP failure table against the text instead of the pattern
- Using a rolling hash modulo a small constant, making collisions common enough to matter
- Reaching for KMP when a library indexOf is both correct and faster in practice