ii. String Hashing

Map strings to numbers so that substring comparison becomes $O(1)$: polynomial hashing modulo the Mersenne prime $2^{61}-1$ with a random base. Simple, general, and the fastest route to most string solutions, provided you defend against anti-hash tests. The probability theory (Schwartz–Zippel, birthday bound, Thue–Morse attack) is also in Randomized Hashing.

$H(s)={\sum }_{i<n}{s}_i{B}^{n-1-i}\mathrm{mod}M,H(s[l..r))=h_r-h_l\cdot B^{r-l},H(st)=H(s)B^{|t|}+H(t).$

Task	Method
substring equality	compare hashes, $O(1)$
compare substrings lexicographically, LCP of two suffixes	binary search the LCP on hashes, then one character: $O(\log n)$
pattern matching (Rabin–Karp), 2D pattern matching	rolling / prefix hashes; hash rows, then hash the column of row hashes with a second, independent base (one base for both directions makes the hash depend only on anti-diagonal sums and collide deterministically)
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)$
is $s[l..r)$ a palindrome; longest palindrome	forward vs reversed-string hash, $O(1)$; binary search
strings under point updates	segment tree of (hash, length) merged by $H(st)$
isomorphic substrings (letter bijection)	26 indicator hashes, compare sorted (CF 985F)
trees, multisets, sets	tree hashing, $\sum f(x)$ with random $f$, XOR of random words (Zobrist)

Modulus	Verdict
$2^{64}$ (unsigned overflow)	never: the Thue–Morse string collides for every base in $O(\log )$ length
$10^9+7$, $2^{31}-1$	too small for many distinct strings (1% birthday collision at about 4500 / 6500 strings); fine for one pattern match
$2^{61}-1$	the default: Mersenne prime, reduction by shift and add, 1% collision only at $\approx 2\cdot 10^8$ strings
two primes near $10^9$ (double hashing)	equivalent strength ($\approx 10^{18}$), two multiplications

Defences, in order: (1) randomise the base at runtime (defeats every precomputed test); (2) $M=2^{61}-1$ (a birthday attack needs $\approx 1.5\cdot 10^9$ candidates); (3) double hashing; (4) never rely on $2^{64}$ overflow; (5) verify on a hash match when candidates are few (makes Rabin–Karp’s output deterministic). On Codeforces assume every hashing problem has an anti-hash test.

using u64 = unsigned long long; using u128 = unsigned __int128;
struct StringHash {                                         // mod 2^61 - 1, random base shared by all instances
    static constexpr u64 M = (1ULL << 61) - 1;
    static u64 mul(u64 a, u64 b) { u128 c = (u128)a * b; u64 r = (u64)(c & M) + (u64)(c >> 61); return r >= M ? r - M : r; }
    static u64 add(u64 a, u64 b) { a += b; return a >= M ? a - M : a; }
    static inline const u64 B = [] { mt19937_64 g(chrono::steady_clock::now().time_since_epoch().count()); return uniform_int_distribution<u64>(1ULL << 40, M - 2)(g); }();
    static inline vector<u64> pw{1};
    static void grow(int n) { while (sz(pw) <= n) pw.push_back(mul(pw.back(), B)); }
    static u64 concat(u64 left, u64 right, int rightLen) { grow(rightLen); return add(mul(left, pw[rightLen]), right); }
    string s; vector<u64> h;                                // h[i] = hash of s[0, i)
    StringHash(const string& str) : s(str), h(str.size() + 1, 0) {
        grow(sz(s)); for (int i = 0; i < sz(s); i++) h[i + 1] = add(mul(h[i], B), (u64)(unsigned char)s[i] + 1);
    }
    u64 get(int l, int r) const { u64 x = h[r] + M - mul(h[l], pw[r - l]); return x >= M ? x - M : x; }   // [l, r)
    static int lcp(const StringHash& a, int l1, int r1, const StringHash& b, int l2, int r2) {
        int lo = 0, hi = min(r1 - l1, r2 - l2);
        while (lo < hi) { int mid = (lo + hi + 1) / 2; if (a.get(l1, l1 + mid) == b.get(l2, l2 + mid)) lo = mid; else hi = mid - 1; }
        return lo;
    }
    static int compare(const StringHash& a, int l1, int r1, const StringHash& b, int l2, int r2) {   // -1, 0, 1
        int k = lcp(a, l1, r1, b, l2, r2), n1 = r1 - l1, n2 = r2 - l2;
        if (k == n1 || k == n2) return (n1 > n2) - (n1 < n2);
        return a.s[l1 + k] < b.s[l2 + k] ? -1 : 1;
    }
};
struct PalindromeHash {                                     // O(1) palindrome test of s[l, r)
    StringHash f, b; int n;
    PalindromeHash(const string& s) : f(s), b(string(s.rbegin(), s.rend())), n(sz(s)) {}
    bool isPal(int l, int r) const { return f.get(l, r) == b.get(n - r, n - l); }
};
vector<int> rabinKarp(const string& text, const string& pat) {   // verified on hash match: exact output
    vector<int> res; int n = sz(text), m = sz(pat); if (m == 0 || m > n) return res;
    StringHash ht(text), hp(pat); u64 target = hp.get(0, m);
    for (int i = 0; i + m <= n; i++) if (ht.get(i, i + m) == target && text.compare(i, m, pat) == 0) res.push_back(i);
    return res;
}
vector<pair<int, int>> find2D(const vector<string>& T, const vector<string>& P) {   // all top-left corners where P occurs in T
    int R = sz(T), C = sz(T[0]), r = sz(P), c = sz(P[0]); vector<pair<int, int>> res;
    if (r > R || c > C) return res;
    using SH = StringHash;                                   // rows use SH::B; columns need an INDEPENDENT base B2
    static const u64 B2 = [] { mt19937_64 g(chrono::steady_clock::now().time_since_epoch().count() ^ 0x9e3779b97f4a7c15ULL); return uniform_int_distribution<u64>(1ULL << 40, SH::M - 2)(g); }();
    vector<SH> rows; for (auto& row : T) rows.emplace_back(row);
    u64 ph = 0; for (int i = 0; i < r; i++) ph = SH::add(SH::mul(ph, B2), SH(P[i]).get(0, c));
    u64 B2r = 1; for (int i = 0; i < r; i++) B2r = SH::mul(B2r, B2);
    for (int j = 0; j + c <= C; j++) {                      // hash of the column of row hashes, rolled downwards
        u64 x = 0;
        for (int i = 0; i < R; i++) {
            x = SH::add(SH::mul(x, B2), rows[i].get(j, j + c));
            if (i >= r) { x = x + SH::M - SH::mul(rows[i - r].get(j, j + c), B2r); if (x >= SH::M) x -= SH::M; }
            if (i >= r - 1 && x == ph) res.push_back({i - r + 1, j});
        }
    }
    return res;
}
struct IsomorphicSubstrings {                               // lowercase; are s[x, x+len) and s[y, y+len) isomorphic?
    vector<StringHash> h;
    IsomorphicSubstrings(const string& s) { for (char c = 'a'; c <= 'z'; c++) { string t(sz(s), '0'); for (int i = 0; i < sz(s); i++) if (s[i] == c) t[i] = '1'; h.emplace_back(t); } }
    bool query(int x, int y, int len) const {
        array<u64, 26> a, b; for (int c = 0; c < 26; c++) a[c] = h[c].get(x, x + len), b[c] = h[c].get(y, y + len);
        sort(all(a)); sort(all(b)); return a == b;
    }
};

Proof: collision bounds, the $2^{61}-1$ reduction and the isomorphism test

Collision bound. For fixed distinct strings $s\ne t$ of length $\le n$, $H(s)-H(t)$ is the value at $B$ of a non-zero polynomial of degree $<n$ over the field ${\mathbb{F}}_M$ (the character map $c\mapsto c+1$ keeps coefficients non-zero and distinct for distinct characters), which has at most $n-1$ roots, so for uniform $B$, $\mathrm{Pr}[\text{collision}]\le \frac{n-1}{M}$ (Schwartz–Zippel in one variable); a union bound over $q$ comparisons gives $\le \frac{qn}{M}$, about $4\cdot 10^{-7}$ for $n=q=10^6$. The bound needs $B$ random and unknown to the adversary: a fixed $(B,M)$ falls to an offline birthday search in $O(\sqrt{M})$, and modulo $2^{64}$ the Thue–Morse strings ${\tau }_k$, ${\bar{\tau }}_k$ satisfy $H({\tau }_k)-H({\bar{\tau }}_k)=\pm {\prod }_{j<k}(B^{2^j}-1)$, divisible by $2^{k(k+1)/2}$ for odd $B$ (and even $B$ fails trivially), so $k=11$ collides for every base. Birthday: $k$ random values in $M$ buckets collide with probability $\approx 1-e^{-k^2/2M}$.

Reduction. $2^{61}\equiv 1(\mathrm{mod}M)$, so a 122-bit product $c=c_{hi}{2}^{61}+c_{lo}$ is congruent to $c_{hi}+c_{lo}<2M$, and one conditional subtraction finishes. Substring hash: $h_r=h_l{B}^{r-l}+H(s[l..r))$ by expanding the Horner recurrence, which is also why concatenation composes. 2D: with bases $B_1$ (rows) and $B_2$ (columns) the grid hash is ${\sum }_{t,k}{g}_{tk}{B}_2^{r-1-t}{B}_1^{c-1-k}$, a non-zero bivariate polynomial of total degree $<r+c$ for different grids, so Schwartz–Zippel gives collision probability $\le \frac{r+c}{M}$; with $B_1=B_2$ it degenerates to ${\sum }_{t+k}$ (anti-diagonal sums) and distinct grids such as rows baba, baba vs bbab, abaa collide for every base. Isomorphism: a letter bijection $f$ maps the indicator string of $c$ in the first substring to the indicator of $f(c)$ in the second, so the multisets of indicator strings agree; conversely, non-zero indicator strings of different letters have disjoint supports, so equal multisets match letters bijectively (all-zero indicators pair with each other) and this matching maps one substring onto the other. Checked against direct comparison on random strings (including 2D search and palindromes).

Rolling hash

$H_{\text{new}}=(H_{\text{old}}-s_{\text{out}}{B}^{k-1})B+s_{\text{in}}(\mathrm{mod}M)$ (add a multiple of $M$ before subtracting). Prefix hashing is strictly more capable (arbitrary substrings) and almost always what you want; rolling matters for streaming input and $O(1)$ memory.

	rolling hash	prefix hashing
memory	$O(1)$	$O(n)$
arbitrary substring	no	$O(1)$
streaming input	yes	no

Content-defined chunking (Rabin fingerprinting): cut a stream where the rolling hash has $k$ trailing zero bits; boundaries depend on content, so inserting bytes does not shift later chunks (rsync, deduplicating backups). Buzhash (cyclic polynomial): $H=\mathrm{rot}(H,1)\oplus \mathrm{rot}(h(s_{\text{out}}),k)\oplus h(s_{\text{in}})$: no multiplication, weaker guarantees. Choose the base at random in $[\sigma ,M-2]$, larger than the alphabet.

Hashing vs deterministic structures

	hashing	suffix automaton / array
code	about 30 lines	40–90 lines
correctness	probabilistic	exact
substring compare	$O(1)$	$O(1)$ after an $O(n\log n)$ build
count distinct substrings	$O(n^2)$	$O(n)$
anti-test risk	real, mitigable	none

Hashing is the right first tool; switch to a suffix automaton or suffix array to enumerate or count over all substrings.

Related notes

• Randomized Hashing and Verification (Thue–Morse attack, multiset hashing)
• Other Matching (Rabin–Karp, wildcard matching)
• Palindromes