Rabin-Karp
Rabin-Karp hashes the pattern once, then hashes each window of the text in turn — each one obtained from the last by dropping the leading character and adding the trailing one, which costs a fixed amount of arithmetic rather than a pass over the window. When a window’s hash equals the pattern’s, the characters are compared to see whether it is a real match or a collision.
How far it jumps
Do not jump at all — compare a number, and verify every hit.
When it is the right choice
Its real home is searching for many patterns at once, since one pass over the text can be checked against a whole set of hashes, and plagiarism detection and file-difference tools use it for exactly that. For one pattern it rarely beats Boyer-Moore, because it looks at every character of the text and skips nothing. The reason it is here is the verification step, which is the honest part almost every description leaves out.
How it works
- Compute the hash of the pattern.
- Compute the hash of the first window of the text, of the same length.
- Compare the two numbers. If they differ, this window cannot contain the pattern and no characters are compared at all.
- If they agree, compare the characters: the window is a candidate, not a match.
- Roll the hash to the next window — subtract the leading character’s contribution, multiply, add the new trailing character — and repeat.
Worth noticing
- The modulus here is 101, which is absurdly small on purpose. A real implementation uses a large prime and collisions become rare; a tool that used one would never show you a collision at all, which teaches the opposite of the truth.
- The collisions counter and the occurrences counter are different numbers, and on the hash-collision scenario the first is larger. That difference is the whole page.
- The skipped counter stays at zero. Rabin-Karp does not skip positions; it makes each position cheaper. That is a different saving, and it is worth not confusing the two.
Cost
- Best
- O(n + m)
- Average
- O(n + m)
- Worst
- O(n · m)
- Extra space
- O(1)
- Longest text
- 160 characters
- Longest pattern
- 24 characters
The limits are pedagogical rather than technical: one column is drawn per character, and a run has to stay short enough to sit and watch. A text and pattern that would take more than three thousand steps on this algorithm are refused before a single step is generated — and because that depends on the text itself and not only on its length, the tool counts the steps first rather than guessing from a formula.