String hashing
Compare any two substrings in after preprocessing. Probabilistic, modulo with a random base.
When
When you need many substring comparisons and the deterministic algorithm is hard: longest palindrome with binary search, longest substring occurring twice, minimal rotation.
The idea
The word becomes a polynomial in base , modulo a large prime :
With the prefix hashes , the hash of is , in .
Equal words always have equal hashes. For two different words of length , the difference of the hashes is a non-zero polynomial in of degree , with at most roots. With a random the collision probability is about . With and comparisons of words of length , that is below .
The multiplication is done in 128 bits (__uint128_t). The reduction modulo the Mersenne prime uses shifts, with no division.
Why a random base
With a fixed base and modulus, someone can construct two words with the same hash in advance. On Codeforces this happens in hacks: solutions with (unsigned long long overflow) always fail on the Thue–Morse word. The base here is chosen when the program runs.
Pitfalls
- The character becomes , so that
'\0'(or'a'if you subtract'a') does not map to 0. Otherwise and would have the same hash. - The test checks that equal substrings always have equal hashes and that there was no collision in the comparisons of different ones. That does not prove collisions cannot happen; it makes them unlikely.
Code
No main: it goes below the #include lines, using namespace std and using ll = long long.
// Polynomial string hashing modulo the Mersenne prime 2^61 - 1, with a random base.
// get(l, r) = hash of s[l..r) in O(1). Equal strings always have equal hashes; two different
// strings of length n collide with probability at most n / (2^61 - 1) over the choice of base.
struct StringHash {
static constexpr unsigned long long MOD = (1ULL << 61) - 1;
vector<unsigned long long> h;
vector<unsigned long long> pw;
static unsigned long long mul(unsigned long long a, unsigned long long b) {
__uint128_t c = (__uint128_t)a * b;
unsigned long long lo = (unsigned long long)(c & MOD);
unsigned long long hi = (unsigned long long)(c >> 61);
unsigned long long r = lo + hi;
if (r >= MOD) {
r -= MOD;
}
return r;
}
static unsigned long long base() {
static unsigned long long b = 0;
if (b == 0) {
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
b = rng() % (MOD - 1000) + 500;
}
return b;
}
StringHash(const string& s) : h(s.size() + 1, 0), pw(s.size() + 1, 1) {
unsigned long long b = base();
for (size_t i = 0; i < s.size(); i++) {
h[i + 1] = mul(h[i], b) + (unsigned char)s[i] + 1;
if (h[i + 1] >= MOD) {
h[i + 1] -= MOD;
}
pw[i + 1] = mul(pw[i], b);
}
}
unsigned long long get(int l, int r) {
unsigned long long x = h[r] + MOD - mul(h[l], pw[r - l]);
if (x >= MOD) {
x -= MOD;
}
return x;
}
};
Tested on 1,000 random cases against a slow, obviously correct solution, with AddressSanitizer and UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).
Practice on CSES
In order: the first is the plain application, the rest need a twist.
- String Matching · String Algorithms
- Longest Palindrome · String Algorithms
More in the USACO Guide
- Hashing · usaco.guide/gold/hashing
In English, with more problems per level.