Rolling hash: compare windows cheaply
Picture
Windows abc and bcd overlap in b,c. Recomputing a numeric fingerprint from scratch repeats work.
Predict
Does equal hash prove equal strings mathematically?
Walk through the small example
No. Adjacent windows share all but two boundary characters.
Mental model and complete Python solution
A rolling hash is a compact shadow of the current window. Move the shadow cheaply, then inspect the real window whenever the shadow matches the target.
What the function promises: Return all exact match starts for ASCII text and pattern. Hash candidates are verified; empty pattern matches every boundary.
def rolling_find(text, pattern):
if pattern == "": return list(range(len(text)+1))
if len(pattern) > len(text): return []
base, mod, m = 257, 1_000_000_007, len(pattern)
high = pow(base, m-1, mod)
target = window = 0
for a, b in zip(pattern, text[:m]):
target = (target*base + ord(a)) % mod
window = (window*base + ord(b)) % mod
answer = []
for start in range(len(text)-m+1):
if window == target and text[start:start+m] == pattern:
answer.append(start)
if start+m < len(text):
window = (window-ord(text[start])*high) % mod
window = (window*base+ord(text[start+m])) % mod
return answer
assert rolling_find("ababa","aba") == [0,2]
assert rolling_find("abc","") == [0,1,2,3]Work and storage: Expected O(n+m) hashing plus verification cost; adversarial collisions can make verification O(nm).
When to recognize it: Adjacent windows share all but two boundary characters.
Check before applying it: Collisions exist; arithmetic, character encoding, and modulus choices are part of the contract.
Change one rule
Need exact guarantees under adversarial input.
See what changes
Use KMP or another deterministic exact matcher.
Connect
windows: Reuse the entering/leaving window update.
KMP: reuse a matched prefix: KMP guarantees exact matching without hash collisions.