Rolling Hashes Without Hand-Waving

Polynomial Fingerprints

Map each symbol to a nonzero integer. For $S=s_0s_1\dots s_{n-1}$, define $H(S)=(s_0b^{n-1}+s_1b^{n-2}+\dots+s_{n-1})\bmod p$, where $b$ is a base and $p$ is a prime modulus. Positional powers make order significant.

For a length-$m$ window, remove the outgoing highest-power term, shift the remaining polynomial by multiplying by $b$, and append the incoming symbol:

$$H_{i+1}=((H_i-t_i b^{m-1})b+t_{i+m})\bmod p.$$

Normalize negative residues in languages where remainder may stay negative. A left-to-right prefix recurrence gives position-independent substring hashes without inverses. A global-power convention is also valid but requires inverse powers or exponent alignment; mixing formulas is incorrect. Avoid bases $0$ and $1$, use nonzero symbol encodings, and randomize parameters when relying on probabilistic collision bounds.

Prefix Hashes and Substring Queries

Use $P[0]=0$ and $P[i+1]=(P[i]b+s_i)\bmod p$. For the half-open substring $S[l\dots r)$ of length $k=r-l$,

$$H(l,r)=(P[r]-P[l]b^{r-l})\bmod p.$$

Precomputed powers make extraction $O(1)$ after $O(n)$ preprocessing. The result already uses local powers, so no modular inverse is needed. Always compare length alongside the fingerprint. Two independently parameterized hashes reduce collision probability but do not make equality mathematically certain. Concatenation is composable through $H(XY)=H(X)b^{|Y|}+H(Y)\pmod p$.

from dataclasses import dataclass


@dataclass(frozen=True)
class HashParameters:
    modulus: int
    base: int


class PolynomialHash:
    """Inverse-free prefix hashes for one modulus and base."""

    def __init__(self, text: str, parameters: HashParameters) -> None:
        modulus, base = parameters.modulus, parameters.base
        if modulus <= 2:
            raise ValueError("modulus must exceed 2")
        if not 1 < base < modulus:
            raise ValueError("base must lie strictly between 1 and modulus")
        self.text, self.modulus, self.base = text, modulus, base
        self.prefix = [0] * (len(text) + 1)
        self.powers = [1] * (len(text) + 1)
        for i, symbol in enumerate(text):
            encoded = ord(symbol) + 1
            self.prefix[i + 1] = (self.prefix[i] * base + encoded) % modulus
            self.powers[i + 1] = self.powers[i] * base % modulus

    def substring(self, left: int, right: int) -> int:
        if not 0 <= left <= right <= len(self.text):
            raise IndexError("invalid half-open substring range")
        length = right - left
        return (
            self.prefix[right]
            - self.prefix[left] * self.powers[length]
        ) % self.modulus


class DoubleSubstringHash:
    PARAMETERS = (
        HashParameters(1_000_000_007, 911_382_323),
        HashParameters(1_000_000_009, 97_266_353),
    )

    def __init__(self, text: str) -> None:
        self.text = text
        self.hashes = tuple(PolynomialHash(text, p) for p in self.PARAMETERS)

    def substring(self, left: int, right: int) -> tuple[int, int]:
        return tuple(h.substring(left, right) for h in self.hashes)

    def equal(
        self,
        first_left: int,
        first_right: int,
        second_left: int,
        second_right: int,
        *,
        verify: bool = False,
    ) -> bool:
        if first_right - first_left != second_right - second_left:
            return False
        if self.substring(first_left, first_right) != self.substring(second_left, second_right):
            return False
        return (
            self.text[first_left:first_right] == self.text[second_left:second_right]
            if verify else True
        )


if __name__ == "__main__":
    text = "abracadabra😀abracadabra"
    index = DoubleSubstringHash(text)
    first, second = (0, 11), (12, 23)
    assert text[first[0]:first[1]] == "abracadabra"
    assert text[second[0]:second[1]] == "abracadabra"
    assert index.substring(*first) == index.substring(*second)
    assert index.equal(*first, *second)
    assert index.equal(*first, *second, verify=True)
    assert not index.equal(0, 4, 3, 7)
    assert index.substring(5, 5) == (0, 0)
    print(index.substring(*first))

Collision Analysis

For unequal strings of maximum length $L$, a collision means their nonzero difference polynomial evaluates to zero modulo $p$. Its degree is at most $L-1$, so if the base is sampled uniformly after the strings are fixed, one comparison collides with probability at most $(L-1)/p$.

Across at most $Q$ comparisons, the union bound gives $\Pr[\text{any collision}]\le Q(L-1)/p$ without assuming independence. Fixed public bases do not provide the same adversarial guarantee. Randomize parameters per process or dataset, use a keyed hash at security boundaries, and obtain a product-style double-hash bound only when parameter choices justify independence.

Hash-only equality is Monte Carlo. Verifying the original substrings after a hash match makes the result deterministic and uses the hash only as a fast rejection filter.

Dynamic and Multidimensional Extensions

A segment tree can store (length, forward hash, reverse hash) at each node. The concatenation identity recomputes parents after point updates in $O(\log n)$; comparing forward and reverse hashes gives a probabilistic palindrome test. Implicit balanced trees and ropes extend the same aggregate to insertion, deletion, split, join, and persistence.

A Fenwick tree can maintain globally weighted terms for fixed-length text with point updates, but ranges at different positions must be shifted to a common exponent. In a grid, independent row and column bases define a 2D polynomial; 2D prefixes or separable row-then-column hashes extract rectangles efficiently. Compare dimensions with residues and use independent parameter pairs to reduce structural collisions.

Persistent path copying creates one root per version while sharing unchanged subtrees, supporting historical substring comparisons. In every extension, a hash remains a compact probabilistic certificate rather than a proof.