Substring fingerprints and suffix structures

The exercise answers many inclusive, byte-indexed substring queries on one unchanging string. Comparing two length-k slices directly takes O(k) in the worst case. Prefix fingerprints reuse work across queries, at the price of a possible hash collision. A matching fingerprint is evidence, not a proof.

Derive the prefix recurrence

Choose base B and modulus M. Encode each byte as byte+1, so values lie in 1..256, and define P[0]=0, W[0]=1:

P[i+1] = (P[i] * B + value(s[i])) mod M
W[i+1] = (W[i] * B) mod M

After three bytes, the unreduced polynomial is v0*B² + v1*B + v2. Multiplying the old prefix by B shifts every exponent up one; adding the new byte supplies the constant term. The arrays each need n+1 entries because P[i] represents the half-open prefix s[0:i].

For inclusive endpoints l and r, let k=r-l+1. Expanding P[r+1] separates it into the first l bytes shifted k positions and the wanted final k bytes:

P[r+1] = P[l] * B^k + fingerprint(s[l:r+1])  (mod M)
H(l,r) = (P[r+1] - P[l] * W[k]) mod M

The multiplication is necessary. Subtracting P[l] without shifting removes the wrong powers. Because Go's remainder may be negative, reduce the product, subtract, then add M once if negative; both reduced operands lie in [0,M). Compare lengths before hashes: this formula alone does not encode the length.

Work an example by hand

For easy arithmetic only, encode A=1, B=2, C=3; take B=5 and M=101. For ABAB, the prefixes are [0,1,7,36,81], and powers begin [1,5,25,24,19]. The first AB, [0,1], hashes to 7. The second AB, [2,3], hashes to (81 - 7*25) mod 101 = -94 mod 101 = 7. Their positions differ, but extraction normalizes both substrings to the same exponents.

Try [1,2]: P[3]-P[1]*25 = 36-25 = 11, matching BA's 2*5+1. The exercise uses the actual bytes plus one and much larger constants; do not copy these teaching parameters into its implementation.

Know what a collision means

Under the same toy parameters, AAA gives 31 while BBA gives 61; those differ. But with base 5, modulus 7, AA hashes to 6 and BC hashes to 2*5+3=13 mod 7=6. They are unequal strings with equal length and equal hash. This is not an overflow bug. Mapping many strings to a finite set forces collisions.

Use two prefix/power pairs and require both fingerprints to agree. This greatly reduces accidental matches for ordinary inputs, but fixed public parameters do not supply an unconditional random probability bound against chosen inputs. The reference uses base 911382323 and moduli 1000000007 and 1000000009. Products of reduced values fit signed int64; an arbitrary larger modulus might not. Preprocessing uses O(n) time and space; fingerprint queries use O(1) time.

The supplied implementation additionally compares the original byte slices when both hashes agree. Therefore its returned equality is exact. If V is the sum of lengths of those verified candidates, total time is O(n+q+V), with O(n) auxiliary space. Repeated long equal substrings can make V large. Removing that comparison gives O(n+q) time and makes the result probabilistic; the exercise deliberately requires exact answers and states this tradeoff.

When to choose a suffix structure instead

A suffix array stores starting indices of suffixes in lexical order. For banana, those indices are [5,3,1,0,4,2]: a, ana, anana, banana, na, nana. Adjacent LCP lengths are [1,3,0,0,2]. The longest repeated substring has length 3; it is ana and may overlap itself.

There are n(n+1)/2=21 nonempty substrings counted by positions. Subtract the sum of adjacent LCP values, 6, to get 15 distinct substring values: each sorted suffix contributes all its prefixes except those already shared with its predecessor. A suffix array plus LCP and range-minimum queries can support exact substring equality without scanning every successful match, but building that machinery is outside this exercise. A suffix automaton also represents all substrings; its usual linear construction assumes constant-time transitions for a fixed alphabet. Neither structure is automatically implemented by a rolling hash.

Check your reconstruction

1. Why does [l,r] use P[r+1]? Answer: the prefix array counts bytes, while r is an inclusive index.
2. Can double hashes prove two arbitrary strings equal? Answer: no; verify bytes or use an exact structure when false matches are unacceptable.
3. Is the second byte of a UTF-8 character a valid byte index? Answer: yes for this API; byte slices need not end on Unicode character boundaries.
4. An empty string receives two malformed inclusive queries. Answer: two false results; output length always equals query count.

Princeton's Rabin–Karp implementation shows both rolling arithmetic and the verification step. Its suffix-array implementation provides a separate exact ordering approach.