Rabin-Karp

Rabin-Karp hash-based string matching.

Rabin-Karp

Rabin-Karp is a hash-based string matching algorithm. It compares the hash of the pattern with the hash of each text window.

If the hashes match there is a possible match; for full confidence we compare characters. Hash collisions are resolved by this verification step.

Thanks to the rolling hash, moving from one window to the next takes O(1); average total complexity is O(n+m).

Rolling hash

The rolling hash subtracts the contribution of the outgoing character and adds that of the incoming one when the window shifts right. This avoids recomputing the hash from scratch.

Formula: h = ((h - ord(text[i-m]) * pow_base) * base + ord(text[i])) % mod, where pow_base = base^(m-1) mod mod.

Taking mod prevents large number overflow; the modulus is usually a large prime.

Exercise rabin_karp function

Write rabin_karp(text, pattern). Return the first match index, or -1. Print 7 with print(rabin_karp("merhabatarif", "tarif")).

Show example solution

def rabin_karp(text, pattern):
    # Hash-based matching
    base = 256
    mod = 101
    n, m = len(text), len(pattern)
    if m == 0 or m > n:
        return -1
    ph = 0
    th = 0
    pow_base = 1
    for _ in range(m - 1):
        pow_base = (pow_base * base) % mod
    for i in range(m):
        ph = (ph * base + ord(pattern[i])) % mod
        th = (th * base + ord(text[i])) % mod
    for i in range(n - m + 1):
        if ph == th:
            if text[i:i + m] == pattern:
                return i
        if i < n - m:
            th = ((th - ord(text[i]) * pow_base) * base + ord(text[i + m])) % mod
            if th < 0:
                th += mod
    return -1
print(rabin_karp("merhabatarif", "tarif"))

Test yourself

hash computation

h = (h * base + ord(text[____)) % mod

Show answer

h = (h * base + ord(text[i)) % mod

What is done on a hash collision?
```
if h == pattern_hash:
    ...
```
- Match is accepted
- Search stops
- Verify character by character
- A new modulus is chosen
Show answer

Verify character by character — Hash collisions are verified character by character.
Rabin-Karp concepts

rolling hash

O(1) shift
mod

Large prime
collision

Verification needed
base

256 characters

Next lesson: Boyer-Moore

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies