SyntaxPilot
Courses/Competitive Programming/Lesson 71
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Competitive Programming · Lesson 71 of 90

String hashing (and anti-hash tests)

queued

These are the notes for Competitive Programming episode 71. A polynomial hash gives a string a short fingerprint; with prefix hashes, the hash of any substring takes O(1), so two substrings can be compared in constant time. Echo Check (are two substrings equal?) shows the letter-by-letter brute force (TLE), the popular unsigned long long hash (mod 2^64), and a real anti-hash test: the Thue–Morse string makes two different halves get the same hash. Distinct Chants (count the distinct substrings of length k) shows that a single hash mod 10^9 + 7 loses 513 strings on random data to the birthday paradox. The fix for both: mod 2^61 − 1 with a random base. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The real-life hook

Checking that two copies of a long contract are identical by reading both takes hours. Instead, a computer prints a short checksum on each cover, computed from every word. Different checksums mean different contracts; equal checksums mean almost surely the same. The risk is a collision: two different contracts with the same checksum. Our job is to make collisions so unlikely that they never happen, even when someone tries.

Problem R1 · Echo Check

(Written for this course.)

  • A string s of n lowercase letters, q queries a b len (1-indexed).
  • For each query: is s[a..a+len−1] equal to s[b..b+len−1]? Print YES or NO.
  • n, q ≤ 10^6.
11 4
abracadabra
1 8 4
2 9 3
1 4 2
4 6 1

abra = abra → YES, bra = bra → YES, ab ≠ ac → NO, a = a → YES.

Attempt 1: letter by letter (TLE)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

bool same(const string& s, int a, int b, int len) {
    for (int i = 0; i < len; i++)                // letter by letter
        if (s[a + i] != s[b + i]) return false;
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    string s;
    cin >> n >> q >> s;
    while (q--) {
        int a, b, len;
        cin >> a >> b >> len;
        a--, b--;
        cout << (same(s, a, b, len) ? "YES" : "NO") << "\n";
    }
}
YES
YES
NO
YES

The worst case is a string of equal letters, where no comparison stops early:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

bool same(const string& s, int a, int b, int len) {
    for (int i = 0; i < len; i++)                // letter by letter
        if (s[a + i] != s[b + i]) return false;
    return true;
}

int main() {
    int n = 1000000, q = 1000000;
    string s(n, 'a');                             // aaaa...a
    mt19937 gen(71);
    int yes = 0;
    while (q--) {
        int a = gen() % n, b = gen() % n;
        int len = gen() % (n - max(a, b)) + 1;
        yes += same(s, a, b, len);
    }
    cout << yes << " YES\n";
}
Time Limit Exceeded

The polynomial hash and prefix hashes

  • hash(c0 c1 … ck−1) = c0·B^(k−1) + c1·B^(k−2) + … + ck−1 (mod M): the letters are digits of a number in base B.
  • H[i+1] = H[i]·B + s[i]: the hash of the first i+1 letters (like reading a decimal number left to right).
  • P[i] = B^i.
  • hash(s[l..l+len−1]) = H[l+len] − H[l]·P[len]: remove the prefix, shifted into place. With base 10: 12345 − 12·1000 = 345.
  • O(n) to build, O(1) per substring.

Attempt 2: unsigned long long (mod 2^64)

Overflow does the modulo for free:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

const ull BASE = 131;                           // mod 2^64: overflow does the mod
vector<ull> H, P;
void build(const string& s) {
    int n = s.size();
    H.assign(n + 1, 0), P.assign(n + 1, 1);
    for (int i = 0; i < n; i++) {
        H[i + 1] = H[i] * BASE + s[i];
        P[i + 1] = P[i] * BASE;
    }
}
ull get(int l, int len) {                       // hash of s[l .. l+len-1]
    return H[l + len] - H[l] * P[len];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    string s;
    cin >> n >> q >> s;
    build(s);
    while (q--) {
        int a, b, len;
        cin >> a >> b >> len;
        a--, b--;
        cout << (get(a, len) == get(b, len) ? "YES" : "NO") << "\n";
    }
}
YES
YES
NO
YES
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

const ull BASE = 131;                           // mod 2^64: overflow does the mod
vector<ull> H, P;
void build(const string& s) {
    int n = s.size();
    H.assign(n + 1, 0), P.assign(n + 1, 1);
    for (int i = 0; i < n; i++) {
        H[i + 1] = H[i] * BASE + s[i];
        P[i + 1] = P[i] * BASE;
    }
}
ull get(int l, int len) {                       // hash of s[l .. l+len-1]
    return H[l + len] - H[l] * P[len];
}

int main() {
    int n = 1000000, q = 1000000;
    string s(n, 'a');                             // aaaa...a
    mt19937 gen(71);
    build(s);
    int yes = 0;
    while (q--) {
        int a = gen() % n, b = gen() % n;
        int len = gen() % (n - max(a, b)) + 1;
        yes += get(a, len) == get(b, len);
    }
    cout << yes << " YES\n";
}
1000000 YES

Fast and correct on random tests. But on Codeforces other contestants can hack your solution with their own input.

The anti-hash test: Thue–Morse

  • Letter i is b if popcount(i) is odd, else a: a b b a b a a b b a a b a b b a ….
  • The second half of a Thue–Morse string of length 2^k is the first half with a and b swapped, so the halves differ.
  • Modulo 2^64, the difference of their hashes is a product of factors (B^(2^i) − 1), each even for an odd base; at length 2^11 = 2048 the product has at least 64 factors of 2, so it is 0 mod 2^64: the same hash for any odd base. (An even base is worse: B^64 ≡ 0, so only the last 64 letters matter.)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

const ull BASE = 131;                           // mod 2^64: overflow does the mod
vector<ull> H, P;
void build(const string& s) {
    int n = s.size();
    H.assign(n + 1, 0), P.assign(n + 1, 1);
    for (int i = 0; i < n; i++) {
        H[i + 1] = H[i] * BASE + s[i];
        P[i + 1] = P[i] * BASE;
    }
}
ull get(int l, int len) {                       // hash of s[l .. l+len-1]
    return H[l + len] - H[l] * P[len];
}

int main() {
    int n = 4096;
    string s(n, 'a');
    for (int i = 0; i < n; i++)                  // Thue-Morse: a b b a b a a b ...
        if (__builtin_popcount(i) % 2) s[i] = 'b';
    build(s);
    int len = n / 2;                             // first half vs second half
    cout << "hash says: " << (get(0, len) == get(len, len) ? "YES" : "NO") << "\n";
    cout << "really:    " << (s.substr(0, len) == s.substr(len) ? "YES" : "NO") << "\n";
}
hash says: YES
really:    NO

Problem R2 · Distinct Chants

(Written for this course.)

  • A string s (n ≤ 10^6) and k (1 ≤ k ≤ n): count the distinct substrings of length k.
7 3
abababa

aba, bab, aba, bab, aba → 2 distinct.

Attempt 1: sort the substrings themselves (TLE)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

int brute(const string& s, int k) {             // sort the substrings themselves
    int n = s.size();
    vector<int> idx(n - k + 1);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int i, int j) { return s.compare(i, k, s, j, k) < 0; });
    int cnt = 0;
    for (int t = 0; t < (int)idx.size(); t++)
        if (t == 0 || s.compare(idx[t], k, s, idx[t - 1], k) != 0) cnt++;
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    string s;
    cin >> n >> k >> s;
    cout << brute(s, k) << "\n";
}
2

A million a's with k = 500000: every comparison runs half a million letters.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

int brute(const string& s, int k) {             // sort the substrings themselves
    int n = s.size();
    vector<int> idx(n - k + 1);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int i, int j) { return s.compare(i, k, s, j, k) < 0; });
    int cnt = 0;
    for (int t = 0; t < (int)idx.size(); t++)
        if (t == 0 || s.compare(idx[t], k, s, idx[t - 1], k) != 0) cnt++;
    return cnt;
}

int main() {
    int n = 1000000, k = 500000;
    string s(n, 'a');                             // one chant, repeated
    cout << brute(s, k) << "\n";
}
Time Limit Exceeded

Attempt 2: hashes mod 10^9 + 7

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

const ull MOD = 1000000007;
ull mul(ull a, ull b) { return a * b % MOD; }
const ull BASE = 131;
vector<ull> H, P;
void build(const string& s) {
    int n = s.size();
    H.assign(n + 1, 0), P.assign(n + 1, 1);
    for (int i = 0; i < n; i++) {
        H[i + 1] = (mul(H[i], BASE) + s[i]) % MOD;
        P[i + 1] = mul(P[i], BASE);
    }
}
ull get(int l, int len) {                       // hash of s[l .. l+len-1]
    return (H[l + len] + MOD - mul(H[l], P[len])) % MOD;
}

int fast(const string& s, int k) {              // sort their hashes
    build(s);
    vector<ull> h;
    for (int i = 0; i + k <= (int)s.size(); i++) h.push_back(get(i, k));
    sort(h.begin(), h.end());
    return unique(h.begin(), h.end()) - h.begin();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    string s;
    cin >> n >> k >> s;
    cout << fast(s, k) << "\n";
}
2
1

(the all-a test, instantly). Now a random chant: a million random letters, k = 20. Random pieces differ early, so the brute force is fast here and serves as the checker:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

int brute(const string& s, int k) {             // sort the substrings themselves
    int n = s.size();
    vector<int> idx(n - k + 1);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int i, int j) { return s.compare(i, k, s, j, k) < 0; });
    int cnt = 0;
    for (int t = 0; t < (int)idx.size(); t++)
        if (t == 0 || s.compare(idx[t], k, s, idx[t - 1], k) != 0) cnt++;
    return cnt;
}

int main() {
    int n = 1000000, k = 20;
    mt19937 gen(71);
    string s(n, 'a');
    for (char& c : s) c = 'a' + gen() % 26;          // random letters
    cout << brute(s, k) << "\n";
}
999981
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

const ull MOD = 1000000007;
ull mul(ull a, ull b) { return a * b % MOD; }
const ull BASE = 131;
vector<ull> H, P;
void build(const string& s) {
    int n = s.size();
    H.assign(n + 1, 0), P.assign(n + 1, 1);
    for (int i = 0; i < n; i++) {
        H[i + 1] = (mul(H[i], BASE) + s[i]) % MOD;
        P[i + 1] = mul(P[i], BASE);
    }
}
ull get(int l, int len) {                       // hash of s[l .. l+len-1]
    return (H[l + len] + MOD - mul(H[l], P[len])) % MOD;
}

int fast(const string& s, int k) {              // sort their hashes
    build(s);
    vector<ull> h;
    for (int i = 0; i + k <= (int)s.size(); i++) h.push_back(get(i, k));
    sort(h.begin(), h.end());
    return unique(h.begin(), h.end()) - h.begin();
}

int main() {
    int n = 1000000, k = 20;
    mt19937 gen(71);
    string s(n, 'a');
    for (char& c : s) c = 'a' + gen() % 26;          // random letters
    cout << fast(s, k) << "\n";
}
999468

513 pieces lost: Wrong Answer, on random data, with no hacker.

The birthday paradox

  • With 23 people in a room, two probably share a birthday (365 days): pairs grow like m².
  • m hashes in M values give about m²/(2M) colliding pairs: m = 10^6, M ≈ 10^9 → about 500 (we saw 513).
  • M = 2^61 − 1 ≈ 2.3·10^18: about 2·10^−7 expected collisions for a million random values. (For a polynomial hash with a random base, two fixed different strings of length L collide with probability at most about L/M, still far below 10^−5 here.)
  • A random base, chosen when the program starts, means nobody can prepare a test against your hash.

The fix: mod 2^61 − 1 with a random base

mul multiplies in 128 bits (__uint128_t), so nothing overflows.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

const ull MOD = (1ULL << 61) - 1;                // a huge prime
ull mul(ull a, ull b) { return (__uint128_t)a * b % MOD; }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ull BASE = rng() % (MOD - 1000) + 500;      // random: nobody can plan a test
vector<ull> H, P;
void build(const string& s) {
    int n = s.size();
    H.assign(n + 1, 0), P.assign(n + 1, 1);
    for (int i = 0; i < n; i++) {
        H[i + 1] = (mul(H[i], BASE) + s[i]) % MOD;
        P[i + 1] = mul(P[i], BASE);
    }
}
ull get(int l, int len) {                       // hash of s[l .. l+len-1]
    return (H[l + len] + MOD - mul(H[l], P[len])) % MOD;
}

int main() {
    int n = 4096;
    string s(n, 'a');
    for (int i = 0; i < n; i++)                  // Thue-Morse: a b b a b a a b ...
        if (__builtin_popcount(i) % 2) s[i] = 'b';
    build(s);
    int len = n / 2;                             // first half vs second half
    cout << "hash says: " << (get(0, len) == get(len, len) ? "YES" : "NO") << "\n";
    cout << "really:    " << (s.substr(0, len) == s.substr(len) ? "YES" : "NO") << "\n";
}
hash says: NO
really:    NO
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

const ull MOD = (1ULL << 61) - 1;                // a huge prime
ull mul(ull a, ull b) { return (__uint128_t)a * b % MOD; }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ull BASE = rng() % (MOD - 1000) + 500;      // random: nobody can plan a test
vector<ull> H, P;
void build(const string& s) {
    int n = s.size();
    H.assign(n + 1, 0), P.assign(n + 1, 1);
    for (int i = 0; i < n; i++) {
        H[i + 1] = (mul(H[i], BASE) + s[i]) % MOD;
        P[i + 1] = mul(P[i], BASE);
    }
}
ull get(int l, int len) {                       // hash of s[l .. l+len-1]
    return (H[l + len] + MOD - mul(H[l], P[len])) % MOD;
}

int fast(const string& s, int k) {              // sort their hashes
    build(s);
    vector<ull> h;
    for (int i = 0; i + k <= (int)s.size(); i++) h.push_back(get(i, k));
    sort(h.begin(), h.end());
    return unique(h.begin(), h.end()) - h.begin();
}

int main() {
    int n = 1000000, k = 20;
    mt19937 gen(71);
    string s(n, 'a');
    for (char& c : s) c = 'a' + gen() % 26;          // random letters
    cout << fast(s, k) << "\n";
}
999981
1

Echo Check with the safe hash:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

const ull MOD = (1ULL << 61) - 1;                // a huge prime
ull mul(ull a, ull b) { return (__uint128_t)a * b % MOD; }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ull BASE = rng() % (MOD - 1000) + 500;      // random: nobody can plan a test
vector<ull> H, P;
void build(const string& s) {
    int n = s.size();
    H.assign(n + 1, 0), P.assign(n + 1, 1);
    for (int i = 0; i < n; i++) {
        H[i + 1] = (mul(H[i], BASE) + s[i]) % MOD;
        P[i + 1] = mul(P[i], BASE);
    }
}
ull get(int l, int len) {                       // hash of s[l .. l+len-1]
    return (H[l + len] + MOD - mul(H[l], P[len])) % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    string s;
    cin >> n >> q >> s;
    build(s);
    while (q--) {
        int a, b, len;
        cin >> a >> b >> len;
        a--, b--;
        cout << (get(a, len) == get(b, len) ? "YES" : "NO") << "\n";
    }
}
YES
YES
NO
YES
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

const ull MOD = (1ULL << 61) - 1;                // a huge prime
ull mul(ull a, ull b) { return (__uint128_t)a * b % MOD; }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ull BASE = rng() % (MOD - 1000) + 500;      // random: nobody can plan a test
vector<ull> H, P;
void build(const string& s) {
    int n = s.size();
    H.assign(n + 1, 0), P.assign(n + 1, 1);
    for (int i = 0; i < n; i++) {
        H[i + 1] = (mul(H[i], BASE) + s[i]) % MOD;
        P[i + 1] = mul(P[i], BASE);
    }
}
ull get(int l, int len) {                       // hash of s[l .. l+len-1]
    return (H[l + len] + MOD - mul(H[l], P[len])) % MOD;
}

int main() {
    int n = 1000000, q = 1000000;
    string s(n, 'a');                             // aaaa...a
    mt19937 gen(71);
    build(s);
    int yes = 0;
    while (q--) {
        int a = gen() % n, b = gen() % n;
        int len = gen() % (n - max(a, b)) + 1;
        yes += get(a, len) == get(b, len);
    }
    cout << yes << " YES\n";
}
1000000 YES
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

const ull MOD = (1ULL << 61) - 1;                // a huge prime
ull mul(ull a, ull b) { return (__uint128_t)a * b % MOD; }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ull BASE = rng() % (MOD - 1000) + 500;      // random: nobody can plan a test
vector<ull> H, P;
void build(const string& s) {
    int n = s.size();
    H.assign(n + 1, 0), P.assign(n + 1, 1);
    for (int i = 0; i < n; i++) {
        H[i + 1] = (mul(H[i], BASE) + s[i]) % MOD;
        P[i + 1] = mul(P[i], BASE);
    }
}
ull get(int l, int len) {                       // hash of s[l .. l+len-1]
    return (H[l + len] + MOD - mul(H[l], P[len])) % MOD;
}

bool same(const string& s, int a, int b, int len) {
    for (int i = 0; i < len; i++)                // letter by letter
        if (s[a + i] != s[b + i]) return false;
    return true;
}

int main() {
    mt19937 gen(7);
    for (int t = 1; t <= 500; t++) {
        int n = gen() % 12 + 1;
        string s(n, 'a');
        for (char& c : s) c = 'a' + gen() % 2;
        build(s);
        for (int k = 0; k < 20; k++) {
            int a = gen() % n, b = gen() % n;
            int len = gen() % (n - max(a, b)) + 1;
            if ((get(a, len) == get(b, len)) != same(s, a, b, len)) { cout << "mismatch on test " << t; return 0; }
        }
    }
    cout << "all 500 tests passed";
}
all 500 tests passed

Complexity vs the constraints

Method Build Per query Safe? Verdict
letter by letter — O(len) yes TLE
mod 2^64 (ull overflow) O(n) O(1) no: Thue–Morse hacked / WA
mod 10^9 + 7 O(n) O(1) no: ~500 birthday collisions WA
mod 2^61 − 1, random base O(n) O(1) yes accepted (~0.1 s)
R2: sort substrings — O(n log n · k) yes TLE
R2: sort hashes O(n) O(n log n) total yes (61-bit) accepted

Memory: two arrays of n + 1 unsigned long longs (16 MB for 10^6).

Common mistakes (and the real outputs)

Mistake What you see Why Fix
mod 2^64 (natural overflow) hash says: YES / really: NO Thue–Morse anti-hash test mod 2^61 − 1
one hash mod 10^9 + 7 999468 instead of 999981 birthday paradox a 61-bit modulus (or two 30-bit ones)
a fixed base hacked a test can target your base random base at start
H[l+len] - H[l]*P[len] under a prime without + MOD negative / wrong values subtraction under a modulus add MOD, then % MOD
a * b % MOD with 61-bit numbers wrong hashes (overflow) the product needs 122 bits (__uint128_t)a * b % MOD
letter value 0 (s[i] - 'a') a = aa = aaa leading zeros don't change the number use s[i] or s[i] - 'a' + 1
base smaller than the alphabet easy collisions digits overlap base ≥ 256, random

Mini project

Write a struct StringHash (prefix hashes, get(l, len), concat(h1, h2, len2)) and use it to find, for a string of length 2·10^5, the longest substring that occurs at least twice with binary search on the length. Compare with a suffix-array solution later in the course (episode 77).

Practice

These are the homework problems from the episode.

1. Longest common substring of two strings. If a common piece of length L exists, a common piece of length L − 1 exists too, so binary search on L; for a fixed L, hash every piece of a, sort, and look up every piece of b. O((|a| + |b|) log² n).

2. Is s[l..r] a palindrome? Hash s and its reverse t. s[l..r] reversed is t[n−1−r .. n−1−l]; compare the two hashes. O(1) per query.

Solutions for 1 and 2 (checked against brute force on 100 random tests)
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;

const ull MOD = (1ULL << 61) - 1;
ull mul(ull a, ull b) { return (__uint128_t)a * b % MOD; }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ull BASE = rng() % (MOD - 1000) + 500;

struct Hash {
    vector<ull> H, P;
    Hash(const string& s) : 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], BASE) + s[i]) % MOD;
            P[i + 1] = mul(P[i], BASE);
        }
    }
    ull get(int l, int len) { return (H[l + len] + MOD - mul(H[l], P[len])) % MOD; }
};

int main() {                                        // longest common substring of a and b
    string a, b;
    cin >> a >> b;
    Hash ha(a), hb(b);
    auto common = [&](int len) {                    // is there a common piece of this length?
        if (len == 0) return true;
        vector<ull> seen;
        for (int i = 0; i + len <= (int)a.size(); i++) seen.push_back(ha.get(i, len));
        sort(seen.begin(), seen.end());
        for (int j = 0; j + len <= (int)b.size(); j++)
            if (binary_search(seen.begin(), seen.end(), hb.get(j, len))) return true;
        return false;
    };
    int lo = 0, hi = min(a.size(), b.size());      // a common piece of length L ⇒ one of L − 1
    while (lo < hi) {
        int mid = (lo + hi + 1) / 2;
        if (common(mid)) lo = mid; else hi = mid - 1;
    }
    cout << lo << "\n";
}
xabcdey
zzbcdabc
3
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;

const ull MOD = (1ULL << 61) - 1;
ull mul(ull a, ull b) { return (__uint128_t)a * b % MOD; }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ull BASE = rng() % (MOD - 1000) + 500;

struct Hash {                                       // prefix hashes of one string
    vector<ull> H, P;
    Hash(const string& s) : 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], BASE) + s[i]) % MOD;
            P[i + 1] = mul(P[i], BASE);
        }
    }
    ull get(int l, int len) { return (H[l + len] + MOD - mul(H[l], P[len])) % MOD; }
};

int main() {                                        // q queries: is s[l..r] a palindrome?
    int n, q;
    string s;
    cin >> n >> q >> s;
    string t(s.rbegin(), s.rend());
    Hash fw(s), bw(t);
    while (q--) {
        int l, r;
        cin >> l >> r;
        l--, r--;
        int len = r - l + 1;                        // s[l..r] reversed = t[n−1−r .. n−1−l]
        cout << (fw.get(l, len) == bw.get(n - 1 - r, len) ? "YES" : "NO") << "\n";
    }
}
7 3
racecar
1 7
2 4
1 2
YES
NO
NO

3. Smallest period of every prefix. For a prefix of length m, a period p works iff hash(0, m − p) == hash(p, m − p). Trying every p is O(m) per prefix; the prefix function of the next episode does all prefixes in O(n) total.

Hint

The smallest period of the prefix of length m is m − π[m − 1] (episode 72).

4. Count the distinct substrings of all lengths (n ≤ 5000). For every length k, hash all pieces and count the distinct ones; sum over k. O(n² log n), about 1.2·10^7 hashes for n = 5000.

Hint

Reuse fast(s, k) from R2 for k = 1..n with the 61-bit hash. A suffix array does it in O(n log n) (episode 77).

Quick quiz

// base 10, no modulus, digits as letters
s = "31415"
H = 0 3 31 314 3141 31415
// hash of s[2..4] = ?

A) 415 · B) 1415 · C) 41 · D) 314

Answer

A. H[5] − H[2]·10^3 = 31415 − 31·1000 = 415: the letters 4, 1, 5.

Interview questions

  1. What is a rolling (polynomial) hash? The string read as a number in base B, modulo M; it can be updated letter by letter.
  2. How do you get the hash of any substring in O(1)? Prefix hashes H and powers P: H[r] − H[l]·P[r − l].
  3. Why is mod 2^64 dangerous? It's not a prime field; the Thue–Morse string makes two different strings collide for any odd base.
  4. What's the birthday paradox? m random values in M slots collide about m²/(2M) times: a million hashes mod 10^9 + 7 give ~500 collisions.
  5. Why 2^61 − 1? It's a Mersenne prime close to 2^64, so collisions are very rare and the reduction is cheap with 128-bit multiplication.
  6. Why a random base? So no fixed input can target your hash (hacks, anti-hash tests).
  7. When not to hash? When an exact linear algorithm exists (KMP, Z-function) and correctness must be guaranteed.

Glossary

Term Meaning Example
Hash A short number computed from a string (a fingerprint) get(0, 4)
Polynomial hash Letters as digits in base B, mod M Σ c_i·B^(k−1−i)
Rolling hash A hash updated one letter at a time H[i+1] = H[i]·B + s[i]
Prefix hash Hash of the first i letters, H[i] H[l + len]
Base B The multiplier of the polynomial random, ≥ 500
Modulus M The number the hash is reduced by 2^61 − 1
Collision Two different strings with the same hash Thue–Morse halves
Anti-hash test An input built to make a hash collide Thue–Morse for mod 2^64
Thue–Morse string Letter i = parity of popcount(i) abbabaab…
popcount The number of 1 bits __builtin_popcount(i)
Birthday paradox Collisions appear after about √M values 513 lost pieces
Mersenne prime A prime of the form 2^p − 1 2^61 − 1
__uint128_t g++'s 128-bit unsigned integer (__uint128_t)a * b % MOD
mt19937_64 64-bit Mersenne Twister random generator random base
Hack A test another contestant submits against your solution Codeforces rounds
Checker A slow, surely-correct program to compare with brute on random data
Stress test Fast vs brute force on many random inputs all 500 tests passed
Prefix function Longest border of every prefix (exact, no hashing) next episode

Summary

  • Prefix hashes give any substring's hash in O(1): H[l+len] − H[l]·B^len.
  • mod 2^64 is broken by the Thue–Morse anti-hash test; mod 10^9 + 7 fails the birthday paradox on a million strings.
  • Use mod 2^61 − 1 with 128-bit multiplication and a random base; add M before subtracting.
  • Sorting hashes counts distinct pieces in O(n log n).

Solutions in C++, Java and Python

Problem R1 · Echo Check

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

const ull MOD = (1ULL << 61) - 1;                // a huge prime
ull mul(ull a, ull b) { return (__uint128_t)a * b % MOD; }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ull BASE = rng() % (MOD - 1000) + 500;      // random: nobody can plan a test
vector<ull> H, P;
void build(const string& s) {
    int n = s.size();
    H.assign(n + 1, 0), P.assign(n + 1, 1);
    for (int i = 0; i < n; i++) {
        H[i + 1] = (mul(H[i], BASE) + s[i]) % MOD;
        P[i + 1] = mul(P[i], BASE);
    }
}
ull get(int l, int len) {                       // hash of s[l .. l+len-1]
    return (H[l + len] + MOD - mul(H[l], P[len])) % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    string s;
    cin >> n >> q >> s;
    build(s);
    while (q--) {
        int a, b, len;
        cin >> a >> b >> len;
        a--, b--;
        cout << (get(a, len) == get(b, len) ? "YES" : "NO") << "\n";
    }
}

Java (Math.multiplyHigh gives the high 64 bits of the product; checked on the sample and 10 random tests against the C++ brute force)

import java.io.*;
import java.util.*;

public class Main {
    static final long MOD = (1L << 61) - 1;
    static long BASE;
    static long[] H, P;

    static long mul(long a, long b) {                    // a·b mod 2^61 − 1, using the 128-bit product
        long lo = a * b, hi = Math.multiplyHigh(a, b);
        long r = (lo & MOD) + (lo >>> 61) + (hi << 3);
        r = (r & MOD) + (r >>> 61);
        return r >= MOD ? r - MOD : r;
    }
    static void build(byte[] s, int n) {
        H = new long[n + 1]; P = new long[n + 1]; P[0] = 1;
        for (int i = 0; i < n; i++) {
            H[i + 1] = (mul(H[i], BASE) + s[i]) % MOD;
            P[i + 1] = mul(P[i], BASE);
        }
    }
    static long get(int l, int len) {                    // hash of s[l .. l+len-1]
        long x = H[l + len] - mul(H[l], P[len]);
        return x < 0 ? x + MOD : x;
    }
    static DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
    static int nextInt() throws IOException {
        int r = 0, b = in.read();
        while (b < '0') b = in.read();
        while (b >= '0') { r = r * 10 + b - '0'; b = in.read(); }
        return r;
    }
    static byte[] nextWord(int n) throws IOException {
        byte[] s = new byte[n]; int b = in.read();
        while (b < 'a') b = in.read();
        for (int i = 0; i < n; i++) { s[i] = (byte) b; b = in.read(); }
        return s;
    }

    public static void main(String[] args) throws IOException {
        BASE = Math.floorMod(new SplittableRandom().nextLong(), MOD - 1000) + 500;   // random base
        int n = nextInt(), q = nextInt();
        byte[] s = nextWord(n);
        build(s, n);
        StringBuilder out = new StringBuilder();
        while (q-- > 0) {
            int a = nextInt() - 1, b = nextInt() - 1, len = nextInt();
            out.append(get(a, len) == get(b, len) ? "YES" : "NO").append('\n');
        }
        System.out.print(out);
    }
}

Python (big integers make the modulus easy; slower)

import sys, random
MOD = (1 << 61) - 1
BASE = random.randrange(500, MOD - 500)               # random base

def build(s):
    n = len(s); H = [0] * (n + 1); P = [1] * (n + 1)
    for i, c in enumerate(s):
        H[i + 1] = (H[i] * BASE + c) % MOD            # Python ints don't overflow
        P[i + 1] = P[i] * BASE % MOD
    return H, P

def main():
    data = sys.stdin.buffer.read().split()
    n, q, s = int(data[0]), int(data[1]), data[2]
    H, P = build(s)
    get = lambda l, ln: (H[l + ln] - H[l] * P[ln]) % MOD
    out, pos = [], 3
    for _ in range(q):
        a, b, ln = int(data[pos]) - 1, int(data[pos + 1]) - 1, int(data[pos + 2]); pos += 3
        out.append("YES" if get(a, ln) == get(b, ln) else "NO")
    print("\n".join(out))

main()

Problem R2 · Distinct Chants

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

const ull MOD = (1ULL << 61) - 1;                // a huge prime
ull mul(ull a, ull b) { return (__uint128_t)a * b % MOD; }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ull BASE = rng() % (MOD - 1000) + 500;      // random: nobody can plan a test
vector<ull> H, P;
void build(const string& s) {
    int n = s.size();
    H.assign(n + 1, 0), P.assign(n + 1, 1);
    for (int i = 0; i < n; i++) {
        H[i + 1] = (mul(H[i], BASE) + s[i]) % MOD;
        P[i + 1] = mul(P[i], BASE);
    }
}
ull get(int l, int len) {                       // hash of s[l .. l+len-1]
    return (H[l + len] + MOD - mul(H[l], P[len])) % MOD;
}

int fast(const string& s, int k) {              // sort their hashes
    build(s);
    vector<ull> h;
    for (int i = 0; i + k <= (int)s.size(); i++) h.push_back(get(i, k));
    sort(h.begin(), h.end());
    return unique(h.begin(), h.end()) - h.begin();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    string s;
    cin >> n >> k >> s;
    cout << fast(s, k) << "\n";
}

Java

import java.io.*;
import java.util.*;

public class Main {
    static final long MOD = (1L << 61) - 1;
    static long BASE;
    static long[] H, P;

    static long mul(long a, long b) {                    // a·b mod 2^61 − 1, using the 128-bit product
        long lo = a * b, hi = Math.multiplyHigh(a, b);
        long r = (lo & MOD) + (lo >>> 61) + (hi << 3);
        r = (r & MOD) + (r >>> 61);
        return r >= MOD ? r - MOD : r;
    }
    static void build(byte[] s, int n) {
        H = new long[n + 1]; P = new long[n + 1]; P[0] = 1;
        for (int i = 0; i < n; i++) {
            H[i + 1] = (mul(H[i], BASE) + s[i]) % MOD;
            P[i + 1] = mul(P[i], BASE);
        }
    }
    static long get(int l, int len) {                    // hash of s[l .. l+len-1]
        long x = H[l + len] - mul(H[l], P[len]);
        return x < 0 ? x + MOD : x;
    }
    static DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
    static int nextInt() throws IOException {
        int r = 0, b = in.read();
        while (b < '0') b = in.read();
        while (b >= '0') { r = r * 10 + b - '0'; b = in.read(); }
        return r;
    }
    static byte[] nextWord(int n) throws IOException {
        byte[] s = new byte[n]; int b = in.read();
        while (b < 'a') b = in.read();
        for (int i = 0; i < n; i++) { s[i] = (byte) b; b = in.read(); }
        return s;
    }

    public static void main(String[] args) throws IOException {
        BASE = Math.floorMod(new SplittableRandom().nextLong(), MOD - 1000) + 500;   // random base
        int n = nextInt(), k = nextInt();
        byte[] s = nextWord(n);
        build(s, n);
        long[] h = new long[n - k + 1];
        for (int i = 0; i + k <= n; i++) h[i] = get(i, k);
        Arrays.sort(h);
        int cnt = 0;
        for (int i = 0; i < h.length; i++) if (i == 0 || h[i] != h[i - 1]) cnt++;
        System.out.println(cnt);
    }
}

Python

import sys, random
MOD = (1 << 61) - 1
BASE = random.randrange(500, MOD - 500)               # random base

def build(s):
    n = len(s); H = [0] * (n + 1); P = [1] * (n + 1)
    for i, c in enumerate(s):
        H[i + 1] = (H[i] * BASE + c) % MOD            # Python ints don't overflow
        P[i + 1] = P[i] * BASE % MOD
    return H, P

def main():
    data = sys.stdin.buffer.read().split()
    n, k, s = int(data[0]), int(data[1]), data[2]
    H, P = build(s)
    pk = P[k]
    print(len({(H[i + k] - H[i] * pk) % MOD for i in range(n - k + 1)}))

main()