Rabin–Karp Rolling Hash Matching

Rabin–Karp hashes sliding windows of the text and compares the hash to the pattern hash—expected linear time with a good rolling hash and modulo prime. Collisions require a double-check with real string compare.

Why this shows up in the real world

Plagiarism detectors fingerprint long documents with rolling hashes. Bioinformatics uses similar k-mer hashing for speed.

Core idea (explained for students)

Choose base B and mod M. Rolling update: subtract old char power, multiply by B, add new char—all % M. When hashes match, verify text[i:i+m] == pat.

Try this in Python

def rk_hash(s: str, base: int = 257, mod: int = 10**9 + 7) -> int:
    h = 0
    for c in s:
        h = (h * base + ord(c)) % mod
    return h


print(rk_hash("abc"), rk_hash("ab"))

Common mistakes

• Weak (M, B) pairs create many false positives—always verify on equality.
• Unicode code points as huge base—keep alphabet mapped to small ints.

Key takeaways

• Rabin–Karp shines with many patterns or repeated searches on one text after tuning.
• Know when KMP or built-in find is simpler for one-off substring checks.