Polynomial rolling hash

A hash function turns a string into an integer, in a way that always gives equal strings equal hashes. The reverse is not guaranteed: two different strings can land on the same hash by collisionhash collisionTwo different inputs that produce the same hash value. Rare with a good hash and a large modulus, but never impossible.In the glossary. A well-chosen hash and a large enough modulus make that rare enough to rely on, but never quite impossible.

A rolling hash makes collisions the only cost worth worrying about, because it computes the hash of every substring in a text in O(1) per step after O(N) preprocessing, instead of hashing each substring from scratch.

The polynomial rolling hash formula

Pick a base B, such as 31 or 37, and a modulus M, such as 10**9 + 7 or the prime (1 << 61) - 1. For a string s of length n, the hash is:

hash(s) = (s[0] * B^(n-1) + s[1] * B^(n-2) + ... + s[n-1]) % M

where each s[i] is a numeric value for that character, usually its ASCII code. The leftmost character carries the highest power of B, which is what makes the formula updatable one slide at a time.

Sliding the window one position right removes the old leftmost character and appends a new rightmost one:

new_hash = ((old_hash - s[left] * B^(n-1)) * B + s[right]) % M

Subtracting s[left] * B^(n-1) strips out the leftmost character's contribution. Multiplying by B shifts every remaining character's weight up by one power, since they are all now one position closer to the left edge. Adding s[right] places the new character at weight B^0. Precomputing every power of B from B^0 up to B^(n-1) before the loop starts means the slide never has to recompute a power on the fly.

A worked example

Find every position where a pattern P occurs in a text T, using rolling hashes.

1import sys2
3
4def main() -> None:5    input_data = sys.stdin.read().split()6    if not input_data:7        return8
9    text = input_data[0]10    pattern = input_data[1]11
12    if len(pattern) > len(text):13        return14
15    base = 3116    mod = (1 << 61) - 117
18    pattern_len = len(pattern)19    text_len = len(text)20
21    # Precompute powers22    powers = [1] * (pattern_len + 1)23    for i in range(1, pattern_len + 1):24        powers[i] = (powers[i - 1] * base) % mod25
26    # Hash the pattern27    pattern_hash = 028    for c in pattern:29        pattern_hash = (pattern_hash * base + ord(c)) % mod30
31    # Hash the first window32    window_hash = 033    for i in range(pattern_len):34        window_hash = (window_hash * base + ord(text[i])) % mod35
36    matches = []37    if window_hash == pattern_hash:38        matches.append(0)39
40    # Slide the window41    for i in range(1, text_len - pattern_len + 1):42        # Remove the leftmost character43        left_val = ord(text[i - 1]) * powers[pattern_len - 1]44        window_hash = (window_hash - left_val) % mod45        # Shift left and add the new rightmost character46        window_hash = (window_hash * base + ord(text[i + pattern_len - 1])) % mod47
48        if window_hash == pattern_hash:49            matches.append(i)50
51    for pos in matches:52        print(pos)53
54
55if __name__ == "__main__":56    main()

abacabad ab

0
4

The program precomputes the powers of the base up to the pattern's length, hashes the pattern once, hashes the text's first window of the same length, and then slides that window one character at a time, comparing its hash to the pattern's hash at every position. For text = "abacabad" and pattern = "ab", the two matching windows are at positions 0 and 4, both spelling "ab", which is exactly what the program prints. Matching hashes here is a strong signal, not a proof by itself, since two different windows could in principle collide onto the same hash; with a modulus near 2^61, that risk is small enough to trust on typical contest constraints.

Handling collisions

A single hash function can always collide, in principle. If the risk matters for a problem, run two independent hash functions with different bases or moduli and require both to agree before reporting a match. That drops the collision probability to roughly the product of the two individual probabilities, which is small enough to ignore in practice.

The lighter alternative is one hash with a very large modulus. 10**9 + 7 is common and fast, but it is also common enough that specially crafted test data can be built to break it; the prime (1 << 61) - 1, about 2.3 × 10^18, is large enough that this kind of targeted collision stops being practical, at the cost of slightly more expensive arithmetic. Python's arbitrary-precision integers make working with a modulus this large no harder than working with a small one.

Counting distinct substrings

To count distinct substrings of a fixed length K, hash every window of that length with a rolling hash and store the hashes in a set; the set's size is the count of distinct substrings. This runs in O(N) total, compared to O(N × K) for building each substring explicitly and hashing or comparing it directly, which matters once K grows past a small constant. The one thing to watch is that a collision here quietly undercounts, since two different substrings that happen to share a hash only occupy one slot in the set; a large modulus or double hashing keeps that risk low.

Getting these right

Apply the modulus after every addition and multiplication, not just at the end. Skipping a % M even once lets the running value grow without bound, and Python will not complain, it will just get slower every step as the integers get bigger.

Precompute the power array carefully, since an error there corrupts every hash the rolling formula produces afterward, not just one. Check the power array against a small hand-computed example, and check the first window's hash the same way, before trusting the sliding part of the algorithm.

And treat a single hash match as likely, not certain. If a problem's checker or your own testing shows a hash-based solution failing silently on a specific input, that is the classic sign of a collision, and the fix is a second, independent hash rather than a bigger constant tacked onto the same one.

When rolling hash fits

Rolling hash is the right tool for finding every occurrence of a fixed pattern in a text, and for counting distinct substrings of a fixed length, both in O(N). It fits less well when you need to compare substrings of different, arbitrary lengths against each other, since a hash computed for one length does not tell you anything about a hash computed for another; for that kind of comparison, hashing every substring you actually need once and storing the results in a dictionary is the more direct approach.