Rolling Hash Coding Problems: 4 Questions with Solutions

How rolling hash works, step by step

1. Rabin–Karp compares hashes before characters. Reading digits as a base-10 number mod 13, the pattern 653 hashes to 653 mod 13 = 3, and the first window 314 to 2. Different hashes prove a window cannot match; only equal ones need a digit check.
2. Slide to 141: 3 leaves and 1 enters, so the hash updates in O(1) as ((2 − 3 × 9) × 10 + 1) mod 13 = 11 (9 is the leaving digit's place value, 10² mod 13). That is not 3, so the window is skipped without reading a digit.
3. Slide to 415: drop 1, add 5, and the hash becomes ((11 − 1 × 9) × 10 + 5) mod 13 = 12. That is not 3 either, so again no digit is read.
4. Slide to 159: the update ((12 − 4 × 9) × 10 + 9) mod 13 = 3 equals the pattern's hash, so the digits are checked: 1 ≠ 6 at once — a spurious hit, since 159 and 653 merely share a remainder mod 13.
5. Slide to 592: drop 1, add 2, and the hash becomes ((3 − 1 × 9) × 10 + 2) mod 13 = 7. That is not 3 either, so again no digit is read.
6. Slide to 926: the update ((7 − 5 × 9) × 10 + 6) mod 13 = 3 equals the pattern's hash, so the digits are checked: 9 ≠ 6 at once — a spurious hit, since 926 and 653 merely share a remainder mod 13.
7. Slide to 265: drop 9, add 5, and the hash becomes ((3 − 9 × 9) × 10 + 5) mod 13 = 5. That is not 3 either, so again no digit is read.
8. Slide to 653: the update ((5 − 2 × 9) × 10 + 3) mod 13 = 3 equals the pattern's hash, and all 3 digits agree, so 653 really occurs at index 7.
9. Slide to 535: drop 6, add 5, and the hash becomes ((3 − 6 × 9) × 10 + 5) mod 13 = 2. That is not 3 either, so again no digit is read.
10. 653 occurs at index 7; the windows at 3 and 5 were spurious hits, caught by the digit check. Each slide is O(1), so the scan is O(n + m) expected; a modulus that collides often degrades it towards O(n × m), so real code uses a large prime.

Rolling Hash study plan

All 4 Rolling Hash problems (1 medium and 3 hard) over 4 days, about 3 h 20 min in all — the pattern first, then easiest to hardest. Then move on to Suffix Array.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve this problem.

• Maximum Length of Repeated Subarray Medium

Day 2

Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

• String Matching: All Occurrences Hard

Day 3

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

• Longest Happy Prefix Hard

Day 4

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

• Shortest Palindrome Hard

Next topic: Suffix Array

Rolling Hash: the essentials

When to reach for it

Many substring comparisons: every window of length m against a pattern, every window of one array against every window of another, every prefix against the suffix of the same length. "The longest repeated" or "the longest common" piece adds a Binary Search on the length, since a repeat of length L contains repeats of every shorter length.

The pattern

Read a window as the digits of a number in base B, modulo a large prime M. To slide one step, subtract the outgoing character times Bᵐ⁻¹, multiply by B, add the incoming character and reduce. Equal windows always hash alike and unequal ones rarely do, so on a match compare the characters, or keep two hashes with different moduli. Prefix hashes give any substring's hash in O(1).

def find_all(text, pattern, B=256, M=(1 << 61) - 1):
    m, hp, hw = len(pattern), 0, 0
    top = pow(B, m - 1, M)              # weight of the outgoing character
    for a, b in zip(pattern, text):
        hp, hw = (hp * B + ord(a)) % M, (hw * B + ord(b)) % M
    out = []
    for i in range(len(text) - m + 1):
        if hw == hp and text[i:i + m] == pattern:   # confirm: hashes collide
            out.append(i)
        if i + m < len(text):
            hw = ((hw - ord(text[i]) * top) * B + ord(text[i + m])) % M
    return out

Cost

O(n + m) time and O(1) extra space, plus O(m) per confirmation — O(n × m) on aaaa…a, where every window matches; two hashes and no confirming stay linear at a tiny risk.

Common mistakes

• One small modulus: 10⁵ window hashes modulo about 10⁹ in a set give about n² ÷ 2M ≈ 5 false matches.
• A negative value after removing the outgoing character in Java, C++ or JavaScript; add M before the remainder.
• Overflow: with M near 10⁹ and a small base, hash * B fits even JavaScript's 2⁵³; M = 2⁶¹ − 1 needs 128-bit products.
• Weighting the outgoing character by Bᵐ instead of Bᵐ⁻¹.

Start with

• Maximum Length of Repeated Subarray: window hashes plus a binary search on length.
• String Matching: All Occurrences: Rabin–Karp, overlaps included.
• Longest Happy Prefix: prefix and suffix hashes grown together.

All rolling hash problems

Medium (1)

• Maximum Length of Repeated Subarray Array, Binary Search, Dynamic Programming

Hard (3)

• Longest Happy Prefix String, KMP
• Shortest Palindrome String, KMP
• String Matching: All Occurrences String, String Matching

Companies that ask rolling hash problems

• Amazon 3 problems on rolling hash
• Google 3 problems on rolling hash
• Microsoft 2 problems on rolling hash
• Meta 1 problem on rolling hash

Other topics

• Arrays 667 problems
• Strings 282 problems
• Math 213 problems
• Hash Table 202 problems
• Dynamic Programming 195 problems
• Greedy 163 problems
• Sorting 156 problems
• Two Pointers 113 problems
• Matrix 107 problems
• Binary Search 95 problems
• Simulation 88 problems
• Bit Manipulation 83 problems