Where it runs
1. The problem
KMP (step 127) jumps on a mismatch using a table it built from the pattern in advance. Rabin-Karp works differently. It turns each window of text (a piece as long as the pattern) into a single number and compares numbers instead of characters. Comparing two numbers takes one operation, so most positions are thrown out at once. A character-by-character check is needed only when the numbers match. The same trick carries over to searching for many patterns of one length at once and to finding a small picture inside a big one. That is where it pays off most.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedOn LeetCode
Problems that compare many substrings of the same length, such as finding repeats or the longest repeated piece. A rolling hash updates each window in O(1), and a real comparison runs only when two hashes match.
Every window has length 10, so roll a hash across the string and collect the windows whose hash you have already seen.
Binary search on the length, and for each length roll a hash to find a window that appears twice. Confirm a hash match on the text, or use two moduli.
The same binary search on the length, with a rolling hash over numbers in place of letters. At n up to 1000 a table similar to lesson 116 passes too.
n is at most 2000, so for every substring of even length compare its two halves with prefix hashes in O(1), and keep the distinct ones in a Set.