Rolling Hash and Rabin–Karp

Polynomial hashing, prefix hashes, substring hash extraction, modular arithmetic, collision probability, double hashing, and verification when correctness must be guaranteed.

h(s) = s₀·B^(m−1) + s₁·B^(m−2) + … + s_(m−1) (mod M). With prefix hashes H[i] and powers B^i, any substring's hash is H[r] − H[l]·B^(r−l), so comparing two substrings costs O(1) after O(n) preprocessing.

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

The base is chosen at run time, so the output does not depend on it (only the match positions are printed). With modulus 2⁶¹ − 1, the birthday bound puts the chance of *any* collision among a million substrings below 10⁻⁶. When correctness must be guaranteed, verify candidate matches character by character (as Rabin–Karp does here), or use two independent hashes. A fixed, known base and a small modulus (e.g. 2⁶⁴ overflow) can be attacked with crafted inputs (Thue–Morse strings break mod 2⁶⁴ hashing).

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

const u64 MOD = (1ULL << 61) - 1;                        // Mersenne prime: fast reduction, low collision rate
u64 mulmod(u64 a, u64 b) {
    __uint128_t p = (__uint128_t)a * b;
    u64 r = (u64)(p & MOD) + (u64)(p >> 61);
    return r >= MOD ? r - MOD : r;
}
struct Hasher {
    vector<u64> h, pw;
    Hasher(const string& s, u64 B) : h(s.size() + 1, 0), pw(s.size() + 1, 1) {
        for (size_t i = 0; i < s.size(); ++i) { h[i + 1] = (mulmod(h[i], B) + (unsigned char)s[i]) % MOD; pw[i + 1] = mulmod(pw[i], B); }
    }
    u64 get(size_t l, size_t r) const { return (h[r] + MOD - mulmod(h[l], pw[r - l])) % MOD; }   // [l, r)
};

int main() {
    u64 B = 1'000'003 + (u64)chrono::steady_clock::now().time_since_epoch().count() % 1'000'000;   // random base defeats crafted inputs
    string text = "abracadabra abracadabra", pat = "cadabra";
    Hasher ht(text, B), hp(pat, B);
    u64 target = hp.get(0, pat.size());
    cout << "Rabin-Karp matches (hash, then verify characters):";
    for (size_t i = 0; i + pat.size() <= text.size(); ++i)
        if (ht.get(i, i + pat.size()) == target && text.compare(i, pat.size
…

Rabin-Karp matches (hash, then verify characters): 4 16
longest repeated substring length in "banana": 3 ("ana")
chance of any collision among 1e6 substrings with M = 2^61-1: about 2.17e-07

Quiz

? Why verify characters after a hash match in Rabin–Karp?
+ Different strings can share a hash (collision); verification makes the answer certain. :: Expected cost stays linear.
- Hashes are slow. :: Comparison is the extra step.
- To find overlapping matches. :: Unrelated.
- It is not needed with any modulus. :: Collisions are always possible.

? Why choose the base at random at run time?
+ An adversary cannot precompute colliding inputs for an unknown base. :: Defeats anti-hash tests.
- It is faster. :: No.
- To avoid overflow. :: Overflow is handled by the modular multiply.
- It changes the matches found. :: The verified matches are the same.

? What does the binary search in “longest repeated substring” rely on?
+ If a substring of length L repeats, so does one of every shorter length — the predicate is monotonic. :: Binary search on the answer.
- The string being sorted :: Not needed.
- Hashes being sorted :: A hash set is used.
- L being a power of two :: No.