String Hashing

Map each string to a number so that comparing substrings becomes $O(1)$. Simple, general, and the fastest route to a working solution for most string problems — provided you defend against anti-hash tests.

Polynomial hashing

$H(s)=({\sum }_{i=0}^{n-1}{s}_i\cdot B^i)\mathrm{mod}M.$

Precompute prefix hashes and powers, then any substring hash is $O(1)$:

$H(s[l..r])=(h[r+1]-h[l])\cdot B^{-l}(\mathrm{mod}M)$

or, avoiding the inverse, compare $h[r+1]-h[l]$ against $H(t)\cdot B^l$.

struct Hashing {
    static const long long M = (1LL << 61) - 1;      // Mersenne prime
    long long B;
    vector<long long> h, p;
 
    static long long mul(long long a, long long b) {  // mod 2^61-1 without __int128 division
        __uint128_t r = (__uint128_t)a * b;
        long long lo = (long long)(r & M), hi = (long long)(r >> 61);
        long long s = lo + hi;
        return s >= M ? s - M : s;
    }
    Hashing(const string& s, long long base) : B(base), h(s.size()+1, 0), p(s.size()+1, 1) {
        for (size_t i = 0; i < s.size(); i++) {
            h[i+1] = (mul(h[i], B) + s[i]) % M;
            p[i+1] = mul(p[i], B);
        }
    }
    long long get(int l, int r) const {               // inclusive [l, r]
        long long res = (h[r+1] - mul(h[l], p[r-l+1])) % M;
        return res < 0 ? res + M : res;
    }
};

Note this version builds the hash left to right so that get needs no inverse — the cleaner formulation.

Defending against collisions

Anti-hash tests are real

Codeforces problems routinely include tests built to break M = 10^9+7 with a fixed base. The Thue-Morse sequence breaks any base modulo $2^{64}$ in $O(\log )$ length; birthday attacks find collisions for a fixed $(B,M)$ pair in $\sqrt{M}$ tries.

Four defences, in order of effectiveness:

1. Randomise the base at runtime. B = uniform_int_distribution<long long>(256, M-2)(rng) with a time-seeded RNG. This alone defeats every precomputed test.
2. Use $M=2^{61}-1$. A birthday attack needs $\approx 1.5\cdot 10^9$ candidates, which is out of reach inside a submission.
3. Double hashing. Two independent $(B,M)$ pairs, compared as a pair. Effectively $M^2$.
4. Never use unsigned long long overflow ($M=2^{64}$) — it is broken by Thue-Morse strings regardless of the base.

With a random base modulo $2^{61}-1$, the collision probability over $q$ comparisons is about $q^2/2^{62}$ — negligible.

What hashing buys you

Task	Method
Substring equality	compare hashes, $O(1)$
Compare substrings lexicographically	binary search the LCP, then compare one character — $O(\log n)$
Pattern matching	rolling hash over the text
Count distinct substrings of length $k$	hash every window, count distinct
Longest common substring of two strings	binary search the length + hash sets, $O(n\log n)$
Longest palindromic substring	binary search with forward and reverse hashes
Is $s[l..r]$ a palindrome?	compare forward and reverse hashes, $O(1)$
Longest common prefix of two suffixes	binary search on the hash
Match a pattern with wildcards	hashing plus FFT, or per-position checks
Tree hashing	the same idea on tree structures

Palindrome checking in $O(1)$

Keep a second hash of the reversed string. Then $s[l..r]$ is a palindrome iff its forward hash equals the corresponding reverse-string hash — a two-line addition that replaces Manacher for many problems.

Hashing vs the deterministic alternatives

	Hashing	Suffix automaton / array
Code length	~30 lines	40-90 lines
Correctness	probabilistic	exact
Substring compare	$O(1)$	$O(1)$ after $O(n\log n)$ build
Count distinct substrings	$O(n^2)$	$O(n)$
Memory	$O(n)$	$O(n)$ to $O(n\sigma )$
Anti-test risk	real, mitigable	none
Generality	very high	high

Hashing is the right first tool. Switch to a suffix automaton when you need to enumerate or count over all substrings, which hashing cannot do efficiently.

Hashing beyond strings

The same polynomial trick hashes any sequence: arrays of integers, tree shapes, multisets (sum of $f(x)$ over elements, with $f$ a random scramble), and 2D grids (hash rows, then hash the row hashes).

See also: Rolling Hash · Rabin-Karp · Suffix Automaton