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 tos[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
bifpopcount(i)is odd, elsea: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
- What is a rolling (polynomial) hash? The string read as a number in base B, modulo M; it can be updated letter by letter.
- 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]. - 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.
- 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.
- 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.
- Why a random base? So no fixed input can target your hash (hacks, anti-hash tests).
- 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()