AlgoVerse

Rabin–Karp

Treat each window of the text as a number mod q, update it in O(1) with a rolling hash, and compare characters only when the remainders agree.

If the characters are digits, each window of m characters of the text is a number. Instead of comparing strings, compare the numbers mod q:

Read the full explanation ↓
Input:
T="235902314152…" · P="31415" · q=13PDF export

The text 2359023141526739921, the pattern 31415 and q = 13; one real match at shift 6 and one spurious hit at 12 (67399 is also 7 mod 13).

  1. def rabin_karp(T, P, q):
  2. # T and P are strings of digits; each window of m digits is a number, compared mod q first.
  3. n, m = len(T), len(P)
  4. d = 10
  5. h = pow(d, m - 1, q) # the weight of the leading digit, mod q
  6. p = t = 0
  7. for i in range(min(m, n)):
  8. p = (d * p + int(P[i])) % q
  9. t = (d * t + int(T[i])) % q
  10. matches = []
  11. spurious = []
  12. for s in range(n - m + 1):
  13. if p == t:
  14. if T[s:s + m] == P:
  15. matches.append(s)
  16. else:
  17. spurious.append(s)
  18. if s < n - m:
  19. t = (d * (t - int(T[s]) * h) + int(T[s + m])) % q
  20. return matches

Invariant: At shift s, t equals the number T[s..s+m−1] mod q.

Start

0123456789101112131415161718
2359023141526739921
31415
p—
t—
matches—
spurious—

Local variables

T'2359023141526739921'
P'31415'
q13

Orange = changed in this step

Call stack

  1. rabin_karp()line 1
Step 1 of 88
Black = compare · Orange = key stepcompare: 0/15 · hashes: 0/1 · roll: 0/14 · hit: 0/1 · spurious_hit: 0/1
    Explanation

    The idea

    If the characters are digits, each window of m characters of the text is a number. Instead of comparing strings, compare the numbers mod q:

    • the next window's remainder comes from the last one in O(1) (a rolling hash): subtract the leading digit with weight 10^(m−1), multiply by 10 and add the new digit;
    • if the remainders differ, there is surely no match;
    • if they agree, there may be one; compare the characters. If not, it is a spurious hit.

    Cost

    With a large random q, spurious hits are rare: O(n + m) expected. In the worst case (say, a uniform text) O((n − m + 1)·m). The idea works for other alphabets too (with the alphabet size as the radix).

    What to watch in the trace

    • The t card is the current window's remainder; compare the "bigger q" and "tiny q" inputs.