Rabin-Karp

Hashes the pattern once, then rolls a window hash across the text in O(1) per shift. Only equal hashes trigger a real comparison. The rolling idea powers plagiarism detection.

Category

Strings

Time complexity

O(n + m) avg

Space complexity

O(1)

Pseudocode

hash the pattern
roll window hash across text
  hash equal → verify chars
  verified → report match

Reference implementation

ph = hash(pat)
wh = hash(text[:m])
for s in range(n - m + 1):
    if wh == ph and verify(s):
        return s
    wh = roll(wh, s)  # O(1)

Open the interactive Rabin-Karp visualisation →