Rolling hashes for pattern search

Strings and tries Senior Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
text, m, base, mod = "abcab", 2, 31, 1_000_003
def h(s: str) -> int:
    v = 0
    for ch in s:
        v = (v * base + ord(ch)) % mod
    return v
windows = [h(text[i:i + m]) for i in range(len(text) - m + 1)]
print(windows[0] == windows[3], windows[0] == windows[1])

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A True False

Right: windows 0 and 3 are both 'ab', and 'ab' differs from 'bc'.

Equal windows always hash equally, but the reverse is only likely, which is why a match is confirmed by comparing characters.

Why not the others?
  • B False False. Equal strings always have equal hashes.
  • C True True. Different strings usually have different hashes.

30-second answer

Treat each window of m characters as a number in some base, modulo a large prime. Moving the window one step removes the leading character's contribution and adds the new one in O(1), so all window hashes cost O(n). When a window's hash equals the pattern's, compare the characters to rule out a collision. Expected O(n + m); worst case O(n × m) if many collisions.

Practise saying it · 45 s. No recording, just a timer

Explain rolling-hash search.

Say your answer out loud, then check which of these points you covered:

  • Window hash in O(1) per step
  • Verify on match
  • Expected O(n + m)

Deep dive

Always confirm a hash match with a real comparison.

Two different moduli make accidental collisions extremely unlikely.

Rolling hashes shine for many patterns of one length and for finding repeated substrings with binary search.

Common mistakes

  • Trusting a hash match without checking the characters.
  • Forgetting to keep values non-negative after subtracting under a modulus.

Senior take & follow-ups

Mention the verification step without being asked.

Follow-up questions

Think of your answer first, then open the hint.

  1. How do you find the longest repeated substring?

    Show hint

    Binary search the length; for each length, look for a repeated window hash.

  2. Why use a prime modulus?

    Show hint

    It spreads values more evenly, which lowers the chance of collisions.

What each operation costs: Trie · KMP Algorithm · Rabin Karp · String Matching

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.