Why this matters when you build with AI
An AI assistant that writes string code often reaches for a hash, because a hash turns "are these two substrings equal?" into "are these two numbers equal?". The first version it writes usually uses the natural overflow of unsigned 64-bit integers as the modulus, with a fixed base such as 131. That version passes the examples in the statement. It also fails on a family of strings that is easy to build once you know the trick, and the failure is silent: two different strings get the same number, the program prints a wrong answer, and nothing crashes.
This lesson builds the hash you should write, explains each choice in it, and shows the test that exposes the weak version. You will use the hash for a standard question: what is the longest substring that appears at least twice?
The idea in plain words
A hash function maps a string to a number. Equal strings must get equal numbers. Different strings usually get different numbers, but not always. When two different strings get the same number, that is a collision.
A rolling hash (also called a polynomial hash) reads the characters of a string as the digits of a number written in some base B, and then reduces the result modulo a number M. For a string s of length n, with c(x) the numeric code of character x:
hash(s) = (c(s[0]) * B^(n-1) + c(s[1]) * B^(n-2) + ... + c(s[n-1])) mod M
Take B = 10, M = 1000 and letters coded as a = 1, b = 2, c = 3. The string "abc" reads as 1 * 100 + 2 * 10 + 3 = 123. The string "cba" reads as 321. These are small numbers so you can check them by hand. In real code, B is a large random number and M is a large prime.
Building the prefix hashes
You do not compute the sum from scratch for every substring. You build one array, where h[i] is the hash of the first i characters:
h[0] = 0, and h[i+1] = (h[i] * B + c(s[i])) mod M
For "abc" with B = 10 and no modulus, the array is 0, 1, 12, 123. Each step multiplies the previous value by the base and adds one character. This is the "rolling" part: one multiply and one add per character, so building the array takes O(n).
Hash of any substring in O(1)
The hash of the substring s[l, r) (the characters from position l up to but not including r) is:
hash(s[l, r)) = h[r] - h[l] * B^(r-l) (mod M)
Worked example with the same numbers. For "abc" and the substring [1, 3), which is "bc":
h[3] - h[1] * B^2 = 123 - 1 * 100 = 23
The hash of "bc" with the same rule is 2 * 10 + 3 = 23. The subtraction removes the part of the number that belongs to the first l characters. Each query needs one multiplication and one subtraction, so it is O(1) once the arrays h and B^i exist. Both arrays take O(n) to build.
Collisions with a small modulus
Now the weakness. Take M = 7 and the same coding. "abc" gives 123, and 123 mod 7 = 4 (since 7 * 17 = 119). "cab" gives 3 * 100 + 1 * 10 + 2 = 312, and 312 mod 7 = 4 (since 7 * 44 = 308). Two different strings of the same length get the same hash, so a comparison that uses only the hash says "equal" for a pair that is not equal.
The size of M controls how often this happens. A random pair of different strings collides with probability about 1/M, if the base is chosen at random. A small M makes collisions common. A large prime M makes them rare, but "rare" is not "never". The rest of this lesson is about making the rare case rare enough and removing the cases an attacker can aim at.
Choosing the modulus and the base
The tempting choice: 2^64
Unsigned 64-bit integers wrap around after 2^64. Writing h = h * B + c with unsigned long long does the modulo for free, with no division and no extra code. Most blog posts and AI-written solutions use exactly this.
The problem is that the wrap-around is not random. Take the Thue-Morse words. Define A_0 = "a", B_0 = "b", and then A_(k+1) = A_k followed by B_k, and B_(k+1) = B_k followed by A_k. The first few are:
A_0 = a B_0 = b
A_1 = ab B_1 = ba
A_2 = abba B_2 = baab
A_3 = abbabaab B_3 = baababbaEach B_k is A_k with the two letters swapped. The lengths double: A_k has length 2^k. These words have a fixed pattern of sign changes, and that pattern makes their hashes equal once the words are long enough. The program below hashes the pairs for three bases with natural 64-bit overflow and prints the first k where the two hashes match:
// Anti-hash demo: Thue-Morse words collide under unsigned 64-bit overflow.
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long u64;
// Polynomial hash with the natural overflow of unsigned 64-bit integers.
u64 hash64(const string& s, u64 base) {
u64 h = 0;
for (unsigned char c : s) h = h * base + c;
return h;
}
int main() {
for (u64 base : {3ULL, 131ULL, 1000003ULL}) {
string A = "a", B = "b"; // A_k and B_k are Thue-Morse words and their complements
int found = -1;
for (int k = 0; k <= 14; k++) {
if (hash64(A, base) == hash64(B, base)) {
found = k;
break;
}
string nA = A + B, nB = B + A;
A = nA;
B = nB;
}
if (found >= 0)
printf("base %llu: A_k and B_k collide at k = %d, length %d\n", base, found, 1 << found);
else
printf("base %llu: no collision up to k = 14\n", base);
}
return 0;
}We compiled it with g++ -O2 -std=c++17 -Wall -Wextra and ran it. The output was:
base 3: A_k and B_k collide at k = 10, length 1024
base 131: A_k and B_k collide at k = 10, length 1024
base 1000003: A_k and B_k collide at k = 10, length 1024The three bases are odd numbers. We also tried base 11400714819323198485 (also odd) with the same result, so four odd bases collided at length 1024 in our runs. We did not try every odd base.
Why does this happen? Here is our own argument, which matches the runs. The difference between the two hash values is a sum of terms (c(a) - c(b)) * B^i with signs that follow the Thue-Morse pattern. That sum factors into a product of terms 1 - B^(2^j) for j from 0 to k-1, up to a sign and a power of B. When B is odd, a power of B is odd, so it is a unit mod 2^64 and can be ignored for divisibility. For odd B, the factor with j = 0 is divisible by 2^1, and each factor with j from 1 to 9 is divisible by 2^(j+2). For k = 10 the powers of 2 add up to 1 + 3 + 4 + ... + 11 = 64, so the difference is divisible by 2^64 and is zero mod 2^64. This argument was written for this lesson and was not checked against a published source in this session.
The practical point does not depend on the argument. Anyone can build a test with these words, and any solution that uses natural 64-bit overflow with a fixed base fails on it. An AI assistant will not warn you about this unless you ask.
The fix: a prime modulus and a random base
A prime modulus gives a clean probability bound. Two different strings of length n give a polynomial in B of degree less than n with nonzero coefficients. Over a prime field such a polynomial has at most n - 1 roots. If B is chosen at random from p values, the chance that it is a root is at most (n - 1) / p.
Use the Mersenne prime p = 2^61 - 1 = 2305843009213693951. We checked with a deterministic Miller-Rabin test in Python that this number is prime. For n = 200000 the bound is about 200000 / 2.3 × 10^18, which is about 9 × 10^-14 for one comparison. That is small even if you compare many pairs, and it does not depend on which strings the test authors chose.
Why 2^61 - 1 and not a random prime? Because multiplying modulo a Mersenne number is cheap. A product of two numbers below 2^61 fits in 122 bits, so the code uses a 128-bit integer for the product. Reducing modulo 2^61 - 1 needs only a mask, a shift and one subtraction, since 2^61 is congruent to 1. The code below does exactly that.
The base must be random and must be picked when the program runs. A fixed base such as 131 can be attacked by a test set that was built against it, as the Thue-Morse example shows. A base chosen from the clock is not known to the authors of the test data. Keep the base above the character codes too: a base of 1 makes the hash the sum of the character codes, so "ab" and "ba" collide at once.
Double hashing as a fallback
If you cannot use 128-bit products, for example on a 32-bit target, use two primes, such as 10^9 + 7 and 998244353 (both checked prime with the same Python test), with two independent random bases. Two strings must match in both hashes to be called equal. The chance of a double collision is roughly the product of the two single chances, but the work doubles. We did not measure double hashing in this lesson, so the speed cost is an estimate, not a result.
The standard code: a hash mod 2^61 - 1 with a random base
The code below is the one to keep. It builds the prefix arrays, answers substring queries in O(1), and finds the longest repeated substring with binary search. It compiles with g++ -O2 -std=c++17 -Wall -Wextra with no warnings. The comments say what each part does.
// Rolling hash mod 2^61-1 with a random base:
// substring hash queries and the longest repeated substring by binary search.
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long u64;
typedef unsigned __int128 u128;
const u64 MOD = (1ULL << 61) - 1;
// (a * b) mod 2^61-1 for a, b below 2^61.
u64 mulmod(u64 a, u64 b) {
u128 x = (u128)a * b;
u64 r = (u64)(x & MOD) + (u64)(x >> 61);
if (r >= MOD) r -= MOD;
return r;
}
u64 addmod(u64 a, u64 b) {
u64 r = a + b;
if (r >= MOD) r -= MOD;
return r;
}
u64 submod(u64 a, u64 b) {
return a >= b ? a - b : a + MOD - b;
}
struct Hasher {
u64 base;
vector<u64> h, pw; // h[i] = hash of s[0, i), pw[i] = base^i
Hasher(const string& s, u64 b) : base(b), h(s.size() + 1, 0), pw(s.size() + 1, 1) {
for (size_t i = 0; i < s.size(); i++) {
h[i + 1] = addmod(mulmod(h[i], base), (u64)(unsigned char)s[i]);
pw[i + 1] = mulmod(pw[i], base);
}
}
// Hash of s[l, r). O(1).
u64 get(size_t l, size_t r) const {
return submod(h[r], mulmod(h[l], pw[r - l]));
}
};
// Random base in [256, MOD - 1].
u64 random_base(mt19937_64& rng) {
return 256 + rng() % (MOD - 256);
}
// Length of the longest substring that occurs at two different start positions.
size_t longest_repeat_len(const string& s, const Hasher& H) {
size_t n = s.size();
auto has_repeat = [&](size_t L) -> bool {
vector<pair<u64, size_t>> v;
v.reserve(n - L + 1);
for (size_t i = 0; i + L <= n; i++) v.push_back({H.get(i, i + L), i});
sort(v.begin(), v.end());
for (size_t i = 1; i < v.size(); i++)
if (v[i].first == v[i - 1].first) return true;
return false;
};
// has_repeat is true for every L up to the answer and false after it.
size_t lo = 0, hi = n;
while (lo < hi) {
size_t mid = (lo + hi + 1) / 2;
if (has_repeat(mid)) lo = mid;
else hi = mid - 1;
}
return lo;
}
int main() {
string s;
cin >> s;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
Hasher H(s, random_base(rng));
printf("%zu\n", longest_repeat_len(s, H));
return 0;
}What we checked
We wrote a brute-force checker in Python. It compares every pair of start positions and takes the longest common prefix. We ran 400 random strings of length 1 to 40, half over the alphabet and half over . The program and the checker agreed on all 400, with 0 mismatches.
We also tested the arithmetic. The mulmod function agreed with a plain 128-bit % MOD on 2000000 random pairs. The get function agreed with direct hashing of every substring of 2000 random strings.
Three hand-checked answers from the program:
abracadabra -> 4 (the substring "abra" appears at positions 0 and 7)
aaaaaa -> 5 ("aaaaa" at positions 0 and 1, overlapping)
banana -> 3 ("ana" at positions 1 and 3, overlapping)Worked problem: longest repeated substring
Here is the problem in full, written for this lesson.
Input: one line with a string s of lowercase letters, with 1 <= |s| <= 200000. Output: the length of the longest substring that occurs at least twice. The two occurrences may overlap, and they must start at different positions.
The key fact is that the property is monotone. If a substring of length L occurs twice, then its prefix of length L - 1 also occurs twice. So "some substring of length L repeats" is true for all L up to the answer and false after it. A monotone yes/no property can be searched with binary search over L.
For one value of L, compute the hash of every substring of length L, sort the n - L + 1 values, and look for two equal neighbours. Equal substrings have equal hashes, so after sorting they sit next to each other. The check costs O(n log n), and binary search adds a factor of about log n, giving O(n log^2 n) in total.
Running the check on the example strings gives the outputs shown above, and a sort-based check is correct because equal hashes are the only way the code finds a repeat. A collision could make the program report a repeat that is not there. With mod 2^61 - 1 and a random base the chance is negligible, as the bound above shows.
Complexity
Building the prefix arrays costs O(n) time and O(n) memory. Each substring hash costs O(1). The longest repeat costs O(n log^2 n) time and O(n) memory, because each binary search step sorts a list of up to n values.
Common mistakes
A small base lets different strings collide. A base of 1 makes the hash the plain sum of the character codes, so "ab" and "ba" get the same value. The symptom is a wrong answer on strings that have the same letters in a different order. The fix is a random base well above the character codes, at least 256 in the code above.
Natural 64-bit overflow with a fixed base fails on Thue-Morse strings. The symptom is a wrong answer that appears only on long, structured inputs, around length 1024 for the words in this lesson. Random tests do not show it. The fix is a prime modulus and a random base.
Plain 64-bit multiplication overflows. A product of two numbers near 2^61 is near 2^122, which does not fit in 64 bits. The product wraps around and the result is not a valid hash. We wrote the variant that computes a * b % MOD directly, and ran it on three strings:
aaaa -> 1 (correct answer 3)
abracadabra -> 1 (correct answer 4)
banana -> 1 (correct answer 3)The symptom is an answer that is too small, because equal substrings no longer get equal hashes. The fix is the 128-bit product in mulmod.
Mapping a letter to 0. If a is coded as 0 instead of 97, the hash of "a" is 0, and so is the hash of "aa". The leading zero adds nothing to the number. The code above uses the character value (97 for a), so this does not happen. If you change the coding, compare lengths as well as hashes.
Comparing hashes of different lengths. The get function returns a number for any [l, r), and two substrings of different lengths can still have equal numbers by chance. Check r - l before you compare. The practice solution below does this.
Trusting the hash on a single test. A passing run shows only that the test set did not find a collision. The brute-force comparison in this lesson is the minimum check. For a contest, also keep a second hash or a slow exact check on a small random sample.
Using the fixed base from a blog post. A base copied from a tutorial is public, so a test set built against it can hit it. The fix is to draw the base at run time.
Checklist
- Use a prime modulus with a fast reduction, such as 2^61 - 1 with a 128-bit product, or two primes.
- Draw the base at run time from a range well above the character codes.
- Reduce after every addition and every multiplication.
- Make the prefix array and the power array
n + 1long, and check the indices ofget. - Compare hashes only for substrings of equal length.
- Test the code against a brute-force checker on 300 or more random small strings.
- Run the Thue-Morse demo once, so you know your hash is not the 2^64 kind.
Here is a prompt to ask an AI assistant to review rolling hash code. It is written so that a good answer is specific and can be checked.
Review this C++ rolling hash for comparing substrings. Check four things:
(1) every multiplication and addition is reduced, and no 64-bit product overflows,
(2) the base is chosen at run time and is well above the character codes,
(3) substring queries compare only substrings of equal length,
(4) the modulus is prime.
For each problem you find, give a short input that exposes it and say how you would test it.
Do not change the code yet. Say clearly if you did not run anything.A good answer names the exact lines, gives an input that you can run, and says what was run and what was only read. Check the answer by running the input. An answer that says "looks correct" without an input is not finished.
Summary
A rolling hash turns substring comparison into a constant-time check after an O(n) build. The weak version uses 64-bit overflow with a fixed base, and the Thue-Morse words expose it. The version to keep uses 2^61 - 1, a 128-bit product, and a random base chosen at run time. The longest repeated substring follows from binary search on the length, with a sort to find equal hashes at each step. The checks in this lesson were the brute-force comparison, the arithmetic self-tests and the anti-hash demo. We did not test double hashing or measure speed on large inputs.
Practice problems
Each problem asks for a small program. Write your own tests before you look at the answer.
Problem 1: distinct substrings of one length. Input: a string s and a number L. Output: how many different substrings of length L occur in s. Example: abab with L = 2 has the substrings "ab", "ba", "ab", so the answer is 2. Hint: hash every substring of length L, then count the distinct values. Compare your answer with a Python set of substrings on random inputs.
Show the answer
Sort the list of hashes of all length-L substrings, then count the entries that differ from the one before. This is the code from our scratch program. We compiled it with g++ -O2 -std=c++17 -Wall -Wextra, and it agreed with a Python set on 300 random strings.
vector<u64> v;
for (size_t i = 0; i + L <= s.size(); i++) v.push_back(H.get(i, i + L));
sort(v.begin(), v.end());
return unique(v.begin(), v.end()) - v.begin();Our output for abab with L = 2 was 2.
Problem 2: equal-substring queries. Input: a string s, a number q, then q lines, each with four numbers l1 r1 l2 r2. For each query print EQUAL if s[l1, r1) and s[l2, r2) are the same string, and DIFFERENT otherwise. Example input: abcabc, 2 queries, 0 3 3 6 and 0 2 1 3. Hint: check the lengths first, then compare the two hash values with get.
Show the answer
Check the lengths, then compare the hashes. The check r1 - l1 == r2 - l2 is needed because a hash of two different lengths can still match by chance. We ran this on the example input and got:
EQUAL
DIFFERENTThe first query compares "abc" with "abc". The second compares "ab" with "bc".
Problem 3: the longest substring that occurs three times. Input: one string s. Output: the length of the longest substring that occurs at least three times, with overlaps counted. Examples: aaaaa gives 3 (the substring "aaa" starts at 0, 1 and 2), and abcabcabx gives 2 (the substring "ab" starts at 0, 3 and 6). Hint: the binary search works the same way as in the lesson. Instead of two equal neighbours, look for three equal values in a row. Check this on random strings against a brute force that counts occurrences.
Show the answer
Keep the binary search, and change the check: after sorting the hashes of all length-L substrings, look for a value that equals the value two positions earlier. Equal values are next to each other after sorting, so three equal values in a row means a value that matches the one two positions back. Our run on 300 random strings agreed with a brute-force count, with 0 mismatches. The outputs were:
aaaaa -> 3
abcabcabx -> 2Problem 4: check the anti-hash demo with a safe modulus. Use the Thue-Morse words A_10 and B_10 from the demo, which have length 1024. Choose 1000 random bases below 2^61 - 1, and count how many of them give equal hashes for A_10 and B_10 under mod 2^61 - 1. Hint: the random base function from the lesson gives you bases in the right range. Predict the count before you run it.
Show the answer
Our run used the same words, a fixed seed, and the same mulmod as the lesson. It gave 0 collisions in 1000 bases, which matches the bound: the difference is a polynomial of degree at most 1023 in the base, so each base has a chance of at most 1023 / (2^61 - 1), about 4 × 10^-16, of giving a collision. The output line was:
length 1024, 1000 random bases: 0 collisions mod 2^61-1Your count may differ if you choose different bases. A count above 0 would mean a bug, not bad luck, because the bound is so small.