uniolympiads Ελληνικά

String hashing

Compare any two substrings in O(1)O(1) after O(n)O(n) preprocessing. Probabilistic, modulo 261−12^{61} - 1 with a random base.

When

When you need many substring comparisons and the deterministic algorithm is hard: longest palindrome with binary search, longest substring occurring twice, minimal rotation.

The idea

The word becomes a polynomial in base bb, modulo a large prime pp:

h(s0…sk−1)=∑i=0k−1c(si) bk−1−i mod p.h(s_0 \dots s_{k-1}) = \sum_{i=0}^{k-1} c(s_i)\, b^{k-1-i} \bmod p .

With the prefix hashes HiH_i, the hash of sl…sr−1s_l \dots s_{r-1} is Hr−Hl br−l(modp)H_r - H_l\, b^{r-l} \pmod p, in O(1)O(1).

Equal words always have equal hashes. For two different words of length kk, the difference of the hashes is a non-zero polynomial in bb of degree <k< k, with at most k−1k - 1 roots. With a random bb the collision probability is about k/pk / p. With p=261−1p = 2^{61} - 1 and 10610^{6} comparisons of words of length 10610^{6}, that is below 10−610^{-6}.

The multiplication is done in 128 bits (__uint128_t). The reduction modulo the Mersenne prime uses shifts, with no division.

Why a random base

With a fixed base and modulus, someone can construct two words with the same hash in advance. On Codeforces this happens in hacks: solutions with p=264p = 2^{64} (unsigned long long overflow) always fail on the Thue–Morse word. The base here is chosen when the program runs.

Pitfalls

  • The character becomes c(si)=si+1c(s_i) = s_i + 1, so that '\0' (or 'a' if you subtract 'a') does not map to 0. Otherwise a\texttt{a} and aa\texttt{aa} would have the same hash.
  • The test checks that equal substrings always have equal hashes and that there was no collision in the 2⋅1052 \cdot 10^5 comparisons of different ones. That does not prove collisions cannot happen; it makes them unlikely.

Code

No main: it goes below the #include lines, using namespace std and using ll = long long.

cpp/string-hashing.cpp
// Polynomial string hashing modulo the Mersenne prime 2^61 - 1, with a random base.
// get(l, r) = hash of s[l..r) in O(1). Equal strings always have equal hashes; two different
// strings of length n collide with probability at most n / (2^61 - 1) over the choice of base.

struct StringHash {
    static constexpr unsigned long long MOD = (1ULL << 61) - 1;
    vector<unsigned long long> h;
    vector<unsigned long long> pw;

    static unsigned long long mul(unsigned long long a, unsigned long long b) {
        __uint128_t c = (__uint128_t)a * b;
        unsigned long long lo = (unsigned long long)(c & MOD);
        unsigned long long hi = (unsigned long long)(c >> 61);
        unsigned long long r = lo + hi;
        if (r >= MOD) {
            r -= MOD;
        }
        return r;
    }

    static unsigned long long base() {
        static unsigned long long b = 0;
        if (b == 0) {
            mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
            b = rng() % (MOD - 1000) + 500;
        }
        return b;
    }

    StringHash(const string& s) : h(s.size() + 1, 0), pw(s.size() + 1, 1) {
        unsigned long long b = base();
        for (size_t i = 0; i < s.size(); i++) {
            h[i + 1] = mul(h[i], b) + (unsigned char)s[i] + 1;
            if (h[i + 1] >= MOD) {
                h[i + 1] -= MOD;
            }
            pw[i + 1] = mul(pw[i], b);
        }
    }

    unsigned long long get(int l, int r) {
        unsigned long long x = h[r] + MOD - mul(h[l], pw[r - l]);
        if (x >= MOD) {
            x -= MOD;
        }
        return x;
    }
};

Tested on 1,000 random cases against a slow, obviously correct solution, with AddressSanitizer and UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).

Practice on CSES

In order: the first is the plain application, the rest need a twist.

More in the USACO Guide

In English, with more problems per level.