Polynomial String Hashing — O(1) Substring Comparison with Prefix Hashes

Algorithm Statement#

Polynomial string hashing extends the rolling hash idea to give O(1) hashes of arbitrary substrings after O(n) preprocessing. Define H[i] as the polynomial hash of the prefix s[0..i-1]:

H[i] = s[0] * b^(i-1) + s[1] * b^(i-2) + ... + s[i-1] * b^0 (mod q)

Equivalently, H[i+1] = H[i] * b + s[i] (mod q). Then the hash of substring s[l..r] (inclusive) is:

hash(l, r) = H[r+1] - H[l] * b^(r - l + 1) (mod q)

Once H[] and the powers b^0, b^1, ..., b^n are precomputed, every substring hash query runs in O(1).

Time: O(n) preprocessing, O(1) per substring hash query. Space: O(n) for the prefix hash and power arrays.

Why This Algorithm Matters#

Once you can compare any two substrings in O(1), an entire class of problems collapses. Binary search on the answer plus hash equality solves longest duplicate substring (LC 1044), longest common substring of two strings, and longest repeated substring with at most k mismatches. Without prefix hashing, those problems require suffix automata or suffix arrays — heavier machinery with steeper learning curves.

In competitive programming circles, polynomial hashing is the universal backup. When the official solution uses a suffix automaton, half the contest field beats it with hashing in 30 lines. Codeforces, ICPC, and TopCoder problem setters explicitly account for "the hash solution" when designing constraints. At Google and Meta, candidates who reach for prefix hashing on string problems are flagged as "thinks like a competitive programmer" — usually positive signal.

In production, the same idea backs Merkle trees (where the hash of a node depends on hashes of children), Git's content-addressable object store, and rsync's block-level deduplication. Understanding polynomial hashing teaches you to think about strings algebraically, which is the foundation for all hash-based data structures.

The key shift in mental model: stop comparing strings character by character. Compute a fingerprint once; compare fingerprints forever.

The Core Insight#

The naive way to compare two length-k substrings is O(k). With prefix hashes, the comparison is O(1) — provided you accept that "equal hash" means "equal string with overwhelming probability."

The derivation of the substring formula is pure algebra. Write out H[r+1] and H[l] in full:

H[r+1] = s[0] * b^r + s[1] * b^(r-1) + ... + s[r] * b^0
H[l]   = s[0] * b^(l-1) + s[1] * b^(l-2) + ... + s[l-1] * b^0

Multiply H[l] by b^(r - l + 1) to align it with the high coefficients of H[r+1]:

H[l] * b^(r-l+1) = s[0] * b^r + ... + s[l-1] * b^(r-l+1)

Subtract:

H[r+1] - H[l] * b^(r-l+1) = s[l] * b^(r-l) + s[l+1] * b^(r-l-1) + ... + s[r] * b^0

That is exactly the hash of s[l..r]. The whole technique is one line of polynomial arithmetic.

For collision resistance, use a 61-bit Mersenne prime modulus (1 << 61) - 1, or pair two independent hashes (double hashing) with different bases and moduli. The collision probability for double hashing on n queries is approximately n^2 / q^2, negligible for q ≈ 10^18 and n up to a billion.

Use a base larger than the alphabet, ideally a prime. 31, 53, 131, 257 are common choices. The base must be coprime to the modulus, which any prime base trivially satisfies.

The catch: this hash is deterministic given a fixed base and modulus. If an adversary knows your hash parameters they can construct collisions. The standard defence in competitive programming is to randomise the base at runtime within [256, q - 1], ensuring the adversary cannot precompute attacks.

Visual Dry Run#

String s = "ababa", base b = 31, modulus q = 10^9 + 7. Map a = 1, b = 2.

Build the prefix hash:

H[0] = 0
H[1] = 0 * 31 + 1 = 1                      (hash of "a")
H[2] = 1 * 31 + 2 = 33                     (hash of "ab")
H[3] = 33 * 31 + 1 = 1024                  (hash of "aba")
H[4] = 1024 * 31 + 2 = 31746               (hash of "abab")
H[5] = 31746 * 31 + 1 = 984127             (hash of "ababa")

Powers: b^0 = 1, b^1 = 31, b^2 = 961, b^3 = 29791, b^4 = 923521, b^5 = 28629151.

Query: hash of s[0..2] (substring "aba"):

H[3] - H[0] * b^3 = 1024 - 0 * 29791 = 1024

Query: hash of s[2..4] (substring "aba"):

H[5] - H[2] * b^3 = 984127 - 33 * 29791 = 984127 - 983103 = 1024

Both substrings hash to 1024 — confirming they are equal. The whole computation is two array lookups, one multiplication, and one subtraction. Compare that to the naive O(3) character-by-character check; for length-1000 substrings the speedup is three orders of magnitude.

Solution (Optimal)#

Python — Prefix Hash Class#

class StringHash:
    MOD = (1 << 61) - 1
    BASE = 131
 
    def __init__(self, s: str):
        n = len(s)
        self.h = [0] * (n + 1)
        self.pw = [1] * (n + 1)
        for i, c in enumerate(s):
            self.h[i + 1] = (self.h[i] * self.BASE + ord(c)) % self.MOD
            self.pw[i + 1] = (self.pw[i] * self.BASE) % self.MOD
 
    def get(self, l: int, r: int) -> int:
        """Hash of substring s[l..r] inclusive."""
        return (self.h[r + 1] - self.h[l] * self.pw[r - l + 1]) % self.MOD
 
    def equal(self, l1: int, r1: int, l2: int, r2: int) -> bool:
        if r1 - l1 != r2 - l2:
            return False
        return self.get(l1, r1) == self.get(l2, r2)

JavaScript — Prefix Hash Class#

class StringHash {
  constructor(s, base = 131n, mod = (1n << 61n) - 1n) {
    this.MOD = mod;
    this.BASE = base;
    const n = s.length;
    this.h = new Array(n + 1).fill(0n);
    this.pw = new Array(n + 1).fill(1n);
    for (let i = 0; i < n; i++) {
      this.h[i + 1] = (this.h[i] * base + BigInt(s.charCodeAt(i))) % mod;
      this.pw[i + 1] = (this.pw[i] * base) % mod;
    }
  }
 
  get(l, r) {
    const value = this.h[r + 1] - this.h[l] * this.pw[r - l + 1];
    return ((value % this.MOD) + this.MOD) % this.MOD;
  }
 
  equal(l1, r1, l2, r2) {
    if (r1 - l1 !== r2 - l2) return false;
    return this.get(l1, r1) === this.get(l2, r2);
  }
}

Complexity: O(n) preprocessing, O(1) per query. Constant-factor work per query is roughly four arithmetic operations.

Common Mistakes#

Single hashing in adversarial settings. A single 32-bit hash collides at roughly n = 65000 substrings (birthday bound). For competitive programming on 10^5 length strings, single hashing with a 61-bit prime usually suffices. For LeetCode hard problems where the platform crafts adversarial tests, use double hashing or randomise the base at runtime.

Negative values from subtraction. H[r+1] - H[l] * pw[r-l+1] can be negative before taking % q. Languages with sign-preserving modulo (Python) handle this correctly; in C++ and JavaScript add the modulus once before reducing.

Off-by-one in the substring formula. The formula uses b^(r - l + 1) because the substring has r - l + 1 characters. Using b^(r - l) returns the hash of s[l..r-1] instead.

Using a base equal to or smaller than the alphabet. If the base is 26 and characters are in [0, 25], the leading character vanishes from the hash because 0 * 26^k = 0. Always shift characters to start from 1 (so 'a' maps to 1, not 0) and pick a base larger than the alphabet.

Forgetting that H[0] = 0 and pw[0] = 1. Many bugs trace back to incorrect initialisation of the index-zero entries. Off-by-one is the universal enemy here.

Comparing hashes of substrings with different lengths. The hash function depends on length implicitly through the power of the base. Two unequal-length substrings can never be considered equal, even if hashes coincidentally match — always check lengths first.

Interview Tips#

Show the derivation of the substring formula on the whiteboard. Most candidates know it as a magic incantation; deriving it from H[i+1] = H[i] * b + s[i] impresses interviewers because it shows you understand polynomial arithmetic, not just patterns.

State the collision argument explicitly. With a 61-bit prime modulus, two random distinct strings collide with probability roughly 2^-61 per query. Across 10^9 queries the expected number of collisions is about 10^9 * 2^-61 ≈ 4 * 10^-10. Negligible.

For longest duplicate substring (LC 1044), explain the binary search structure: binary search the length L, then for each candidate L, hash all length-L substrings and check for duplicates with a hash set. Total time O(n log n) — clean and fast.

If asked about double hashing, describe it as "two independent (base, modulus) pairs treated as a tuple key." This sounds professional and is the actual implementation.

For the longest common substring of two strings, binary search on length and hash all length-L substrings of both strings. If any hash from string 1 appears in string 2 at the same length, you have a candidate. This is O((n + m) log min(n, m)).

Follow-up Questions#

Q: Why use a Mersenne prime modulus like 2^61 - 1? A: It supports fast modular reduction with bit shifts (x % (2^61 - 1) = (x & ((1 << 61) - 1)) + (x >> 61) after one correction step). On 64-bit machines this halves the cost compared to general division.

Q: How do you compute the hash of a concatenation given the two parts' hashes? A: If hash(a) has length la and hash(b) has length lb, then hash(a + b) = (hash(a) * b^lb + hash(b)) mod q. This composability is what makes Merkle trees work.

Q: What is the longest common prefix of two suffixes using prefix hashes? A: Binary search on the length: for length L, check if hash(s[i..i+L-1]) == hash(s[j..j+L-1]). Total time O(log n) per query.

Q: How does polynomial hashing relate to fingerprinting? A: Both are randomised hashing techniques where the fingerprint is treated as a stand-in for the original. Karp-Rabin's original paper formalised this for pattern matching; the prefix-hash variant generalises it to substring queries.

Q: Can you use this with non-string sequences? A: Yes. Replace ord(c) with any integer mapping. Polynomial hashing works for arrays, tuples, parsed tokens — anything you can map deterministically to integers in [1, q - 1].

Key Takeaways#

• Prefix hashes turn O(k) substring comparison into O(1) after O(n) preprocessing using the formula hash(l, r) = H[r+1] - H[l] * b^(r-l+1) (mod q).
• The technique works because polynomial hashes compose: shifting the prefix by r - l + 1 positions in the base-b numeral system aligns terms for clean subtraction.
• Use a 61-bit Mersenne prime modulus and a base larger than the alphabet for collision-resistant hashes; use double hashing or randomised bases when adversarial input is possible.
• Initialisation is the source of most bugs: H[0] = 0, pw[0] = 1, characters mapped to start from 1.
• Polynomial hashing unlocks longest duplicate substring, longest common substring, and any binary-search-on-answer string problem in O(n log n).
• Interview signal: deriving the formula from scratch and choosing collision-safe parameters demonstrates the algebraic maturity FAANG interviewers reward.