Reuse the prefix work

P[i+1]=(P[i]*B+v[i]) mod M, P[0]=0. W[i+1]=W[i]*B mod M, W[0]=1.

Derive three terms: v0*B²+v1*B+v2.

Remove the shifted prefix

Inclusive [l,r] has length k=r-l+1.

H(l,r)=(P[r+1]-P[l]*W[k]) mod M.

Predict the failure if W[k] is omitted: the old prefix's powers no longer align.

Try ABAB

A=1, B=2; base=5, modulus=101. Prefixes: 0,1,7,36,81; W[2]=25.

First AB: 7. Second AB: 81-7*25=-94 ≡ 7. Normalize negative remainders. Check length before fingerprint.

Agreement is not equality

Base 5, modulus 7: AA→6, BC→6.

Two moduli reduce accidental collisions; fixed parameters give no adversarial guarantee. Exact byte verification costs the total number of candidate bytes checked.

Choose the right tool

Fingerprint preprocessing O(n), lookup O(1). Reference returns exact results by verifying candidates: O(n+q+V).

Suffix array + LCP + RMQ can avoid repeated long comparisons. banana: sorted starts 5,3,1,0,4,2, adjacent LCP sum 6, so distinct substrings 21-6=15.

Boundary reconstruction

Indices address bytes; r is inclusive. Empty or malformed ranges produce false, preserving output count.

Explain why UTF-8 character counts cannot replace byte counts in this API.