AlgoViz
HomeStrings

Rabin Karp Algorithm

Hard

Roll the hash along the text

Problem

Find all occurrences of a pattern in a text using rolling hashes (Rabin-Karp).

In simple words

Slide a rolling hash of the pattern's length; only compare characters when the hashes match.

The idea

Hash the pattern once, then slide a window of that length through the text updating the hash in O(1) by removing the outgoing character and adding the incoming one. Only when the hashes match do you verify character by character.

The trick

  • Always verify on a hash match — hashes can collide.
  • The rolling update is what makes it O(n + m) on average.
  • A bad hash choice degrades it to O(n·m).
a
b
x
a
b
c
a
b
c
a
b
y
0
1
2
3
4
5
6
7
8
9
10
11

Step 1 of 9. Brute force: slide "abcaby" across the text, comparing letter by letter. Values: a, b, x, a, b, c, a, b, c, a, b, y.

1/9
Brute force
timeO(n·m)spaceO(1)

Slide and compare.

1for (let i = 0; i + m <= n; i++) {2  let j = 0;3  while (j < m && text[i + j] === pat[j]) j++;4  if (j === m) return i;5}

Input

array
[a, b, x, a, b, c, a, b, c, a, b, y]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
text = "abcabcabd", pattern = "abd"
Output:
[6]
Explanation:
The pattern appears starting at index 6.

Example 2

Input:
text = "aaaa", pattern = "aa"
Output:
[0, 1, 2]
Explanation:
Overlapping matches at 0,1,2.

Example 3

Input:
text = "abc", pattern = "xyz"
Output:
[]
Explanation:
No match → empty.

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.