In the previous page, we established that polynomial hashing can transform string comparison from O(m) character-by-character to O(1) integer comparison. But we also identified a critical challenge: if computing each window's hash costs O(m), we lose all the efficiency gains.\n\nThe rolling hash technique solves this beautifully. It exploits the mathematical structure of polynomial hashing to update hash values incrementally as the window slides—computing each new hash in O(1) time based on the previous one, rather than recomputing from scratch.\n\nThis page provides a complete, rigorous treatment of rolling hash mechanics, including the mathematical derivation, modular arithmetic subtleties that trip up many implementations, and production-ready code patterns.

Let's establish the precise mathematical framework for rolling hash. We'll use notation that makes the derivation crystal clear.\n\nDefinitions:\n\n- Text: T = t₀t₁t₂...t_{n-1} (length n)\n- Pattern: P = p₀p₁p₂...p_{m-1} (length m)\n- Base: b (a prime number)\n- Modulus: q (a large prime number)\n- Character value: v(c) = ord(c) for character c\n\nPolynomial hash of a string S = s₀s₁...s_{m-1}:\n\n\nH(S) = Σᵢ₌₀^{m-1} [v(sᵢ) × b^{m-1-i}] mod q\n = v(s₀)×b^{m-1} + v(s₁)×b^{m-2} + ... + v(s_{m-1})×b⁰ mod q\n\n\nThis treats the string as a number in base b. The leftmost character has the highest weight.

The window hash notation:\n\nLet H_i denote the hash of the substring T[i:i+m]:\n\n\nH_i = H(T[i:i+m]) = Σⱼ₌₀^{m-1} [v(t_{i+j}) × b^{m-1-j}] mod q\n\n\nExpanding for a concrete example with m = 5:\n\n\nH_i = v(t_i)×b⁴ + v(t_{i+1})×b³ + v(t_{i+2})×b² + v(t_{i+3})×b¹ + v(t_{i+4})×b⁰\n\n\nSimilarly for the next window:\n\n\nH_{i+1} = v(t_{i+1})×b⁴ + v(t_{i+2})×b³ + v(t_{i+3})×b² + v(t_{i+4})×b¹ + v(t_{i+5})×b⁰\n\n\nCrucial observation: Both expressions share four terms. The structure of polynomial hashing allows us to relate H_{i+1} to H_i algebraically.

Now let's derive the rolling update formula step by step. We want to express H_{i+1} in terms of H_i.\n\nStarting point:\n\n\nH_i = v(t_i)×b^{m-1} + v(t_{i+1})×b^{m-2} + v(t_{i+2})×b^{m-3} + ... + v(t_{i+m-1})×b⁰\n\n\nStep 1: Remove the outgoing character\n\nThe character t_i is leaving the window. Its contribution is v(t_i)×b^{m-1}. We subtract it:\n\n\nH_i - v(t_i)×b^{m-1} = v(t_{i+1})×b^{m-2} + v(t_{i+2})×b^{m-3} + ... + v(t_{i+m-1})×b⁰\n\n\nStep 2: Shift all terms left (multiply by b)\n\nEach remaining character needs its exponent increased by 1 (effectively shifting left in the window):\n\n\n(H_i - v(t_i)×b^{m-1}) × b = v(t_{i+1})×b^{m-1} + v(t_{i+2})×b^{m-2} + ... + v(t_{i+m-1})×b¹\n\n\nStep 3: Add the incoming character\n\nThe character t_{i+m} enters the window at the rightmost position (power b⁰):\n\n\n(H_i - v(t_i)×b^{m-1}) × b + v(t_{i+m}) = H_{i+1}\n

The rolling hash update formula:\n\n\nH_{i+1} = (H_i - v(outgoing) × b^{m-1}) × b + v(incoming) (mod q)\n\n\nWhere:\n- outgoing = t_i (character leaving the left side of window)\n- incoming = t_{i+m} (character entering the right side of window)\n- b^{m-1} is precomputed once at the start\n\nOperation count:\n- 1 multiplication: v(outgoing) × b^{m-1}\n- 1 subtraction: H_i - ...\n- 1 multiplication: ... × b\n- 1 addition: ... + v(incoming)\n- 1 modulo: ... mod q\n\nAll O(1) operations, regardless of window size m!

The rolling hash formula involves modular arithmetic, which introduces subtleties that cause many implementations to fail. Let's address them thoroughly.\n\nWhy we need modular arithmetic:\n\nWithout the mod operation, hash values would grow exponentially:\n\n\nFor a 100-character string with base 31:\nMaximum hash ≈ 127 × 31^99 ≈ 10^149\n\n\nThis vastly exceeds what any integer type can hold (64-bit integers max out around 10^19). The modulus keeps values bounded.\n\nThe negativity problem:\n\nConsider the subtraction in our formula: H_i - v(outgoing) × b^{m-1}\n\nEven though H_i was computed mod q, the term v(outgoing) × b^{m-1} might be larger than the result, producing a negative value. Different programming languages handle negative modulo differently:\n\n\nPython: (-5) % 3 = 1 (always positive)\nC/Java: (-5) % 3 = -2 (sign of dividend)\nJS: (-5) % 3 = -2 (sign of dividend)\n

The corrected rolling update formula:\n\n\nH_{i+1} = ((H_i - v(outgoing) × b^{m-1} % q) × b + v(incoming)) % q\n ↑ ↑ ↑\n Make non-negative Main computation Final reduction\n\n\nIn practice, a robust implementation ensures non-negativity at each step:\n\npython\ntemp = (H_i - v(outgoing) * power_of_base) % q\ntemp = (temp + q) % q # Handle negative result\nH_next = (temp * base + v(incoming)) % q\n

The choice of base b and modulus q significantly affects collision probability and numerical stability. Let's analyze the considerations.\n\nChoosing the base b:\n\nThe base should be:\n1. Larger than the alphabet size — Ensures distinct characters produce distinct contributions\n2. Prime — Reduces collision patterns from multiplicative relationships\n3. Not too large — Prevents overflow during intermediate computations\n\nCommon choices:\n- For ASCII (128 characters): b = 131 or 257\n- For lowercase English (26 characters): b = 31 or 37\n- For Unicode (65536+ characters): b = 65537\n\nThe value 31 is popular because it's prime, works well for lowercase English, and x * 31 = (x << 5) - x can be computed efficiently.

Choosing the modulus q:\n\nThe modulus should be:\n1. Prime — Ensures uniform distribution of hash values\n2. Large — Collision probability ≈ 1/q, larger is better\n3. Safe for multiplication — q² should not overflow your integer type\n\nCommon choices:\n- 10^9 + 7 (fits in 32 bits, q² fits in 64 bits)\n- 10^9 + 9 (another prime, often used with 10^9 + 7 for double hashing)\n- 2^61 - 1 (Mersenne prime, very efficient mod operation)\n- 10^18 + 9 (for 128-bit integers or big integer libraries)\n\nThe 64-bit consideration:\n\nWith base b ≈ 100 and modulus q ≈ 10^9:\n- Maximum intermediate value before mod: (q-1) × b ≈ 10^11\n- This fits comfortably in 64 bits (max ≈ 10^19)\n\nIf you need larger moduli, you'll need 128-bit integers or careful handling.

Now let's build a complete, production-ready rolling hash implementation that handles all edge cases correctly.

Let's trace through a concrete example to see exactly how rolling updates work step by step.\n\nSetup:\n- Text: "ABCDE"\n- Window size: 3\n- Base: 10 (simplified for clarity)\n- Modulus: 1000 (simplified)\n- Character values: A=1, B=2, C=3, D=4, E=5\n\nInitial hash computation (window "ABC"):\n\n\nH₀ = 1×10² + 2×10¹ + 3×10⁰\n = 100 + 20 + 3\n = 123\n\n\nFirst roll: "ABC" → "BCD"\n\n\n Step 1: Remove 'A' contribution\n H - A×10² = 123 - 1×100 = 23\n \n Step 2: Shift left (multiply by base)\n 23 × 10 = 230\n \n Step 3: Add 'D' contribution\n 230 + 4 = 234\n \nH₁ = 234\n\n\nVerification: Direct computation of "BCD":\n\nH("BCD") = 2×10² + 3×10¹ + 4×10⁰ = 200 + 30 + 4 = 234 ✓\n

Second roll: "BCD" → "CDE"\n\n\n Step 1: Remove 'B' contribution\n H - B×10² = 234 - 2×100 = 34\n \n Step 2: Shift left\n 34 × 10 = 340\n \n Step 3: Add 'E' contribution\n 340 + 5 = 345\n \nH₂ = 345\n\n\nVerification: Direct computation of "CDE":\n\nH("CDE") = 3×10² + 4×10¹ + 5×10⁰ = 300 + 40 + 5 = 345 ✓\n\n\nKey observation: Each roll required exactly 3 arithmetic operations (subtract, multiply, add) regardless of window size. If the window were 1000 characters, the update would still take exactly 3 operations.

A production-ready rolling hash must handle various edge cases correctly. Let's examine them:\n\nEdge Case 1: Window equals string length\n\nWhen m = n, there's only one window position. The rolling hash should:\n- Compute the initial hash\n- Return false on first slide attempt\n\nEdge Case 2: Empty string or zero-size window\n\nThese should be handled gracefully (return empty results or raise sensible errors).\n\nEdge Case 3: Single-character window\n\nWhen m = 1:\n- base_power = base^0 = 1\n- Hash of single character = ord(char) mod q\n- Rolling update: new_hash = incoming (outgoing was the entire previous hash)

Let's rigorously analyze the time and space complexity of the rolling hash technique.\n\nTime Complexity:\n\n1. Initialization:\n - Computing base^(m-1): O(log m) using fast exponentiation, or O(m) iteratively\n - Computing initial hash: O(m) for processing m characters\n - Total initialization: O(m)\n\n2. Per-slide operation:\n - Subtraction: O(1)\n - Multiplication: O(1)\n - Addition: O(1)\n - Modulo: O(1)\n - Total per slide: O(1)\n\n3. Processing all positions:\n - n - m + 1 windows total\n - Each window (after first) updated in O(1)\n - Total: O(n - m + 1) = O(n)

Space Complexity:\n\n- String storage: O(n) (assumed already provided)\n- Hash value: O(1)\n- Base power: O(1)\n- Position tracking: O(1)\n- Total auxiliary space: O(1)\n\nComparison with other approaches:\n\n| Approach | Time to hash all windows | Space |\n|----------|-------------------------|-------|\n| Naive (recompute each) | O(nm) | O(1) |\n| Rolling hash | O(n) | O(1) |\n| Precompute all hashes | O(n) | O(n) |\n\nRolling hash achieves optimal time with minimal space.

We've covered the rolling hash technique in complete detail. Let's consolidate the key points:

What's next:\n\nThe rolling hash is the engine of Rabin-Karp, but hashing brings an unavoidable issue: collisions. Two different strings can produce the same hash, leading to false positives. In the next page, we'll explore how Rabin-Karp handles collisions, the impact on complexity, and strategies for minimizing their occurrence.