Loading…

mediumStringsSometimes asked

Rabin–Karp Substring Search (Rolling Hash)

Q: How do you solve Rabin–Karp Substring Search (Rolling Hash) using the Naive — Recompute Each Window approach?

When to use it: Say it first to motivate why an O(1) hash update is worth the modular-arithmetic care. The baseline simply re-derives whether each window equals the pattern from scratch. **The literal method.** Slide a start index `s` across the text, and at each `s` compare the `m` characters of the window with the pattern. Stop early on the first mismatch; record `s` if all `m` match. **The overlap it ignores.** Window starting at `s` and window starting at `s+1` share `m−1` characters. The naive method re-reads those shared characters every step. A rolling hash captures the window in a single number so that shifting reuses almost all prior work. **Worst case.** Text `"aaaa...a"` with pattern `"aaa...ab"` matches `m−1` characters per window before failing — `n` windows × `m` checks ≈ `n·m`. At `n = m = 10⁶` that's 10¹² operations, far too slow. Time complexity: O(n·m). Space complexity: O(1).

Arrays & Hashing · 41 of 83 · 12 min

Given a text t of length n and a pattern p of length m, return all starting indices in t where p occurs, using a rolling hash.

Report overlapping occurrences. Your hash equality must be confirmed by an actual character comparison so that a hash collision never produces a wrong answer.

In plain English

Comparing the pattern against every window directly costs O(m) per window. Rabin–Karp replaces that with an O(1) hash comparison per window by rolling the hash as the window slides. Because different strings can share a hash, a positive hash test must be confirmed with a real comparison — that confirmation is the heart of getting the answer correct.

Examples

Example 1

Input: t = "abedabcabc", p = "abc"
Output: [4, 7]
Note: Windows at 4 and 7 hash equal to p and verify as "abc". Any other coincidental hash matches are rejected by verification.

Example 2

Input: t = "aaaaa", p = "aa"
Output: [0, 1, 2, 3]
Note: Overlapping matches; each adjacent window hashes equal and verifies.

Example 3

Input: t = "abc", p = "d"
Output: []
Note: No window hash equals p's hash; empty result.

Constraints

1 ≤ m ≤ n ≤ 10⁶
Strings are ASCII; treat each character's code as its numeric value
Use a large prime modulus to keep collision probability low
Report overlapping occurrences

Clarifying questions4First question: Do I have to handle hash collisions?Explore questions

Q1.Do I have to handle hash collisions?
Yes. A matching hash is only a candidate; verify the characters. Skipping verification is a correctness bug, not an optimization.
Q2.What modulus and base should I use?
A large prime modulus (e.g. ~10⁹+7) and a base above the alphabet size (e.g. 256 or a random prime). Larger and randomized → fewer collisions.
Q3.Is worst-case O(n·m) acceptable?
Average case is O(n+m); worst case degrades only under pathological collisions. If a guaranteed bound is required, use KMP instead.
Q4.Overlapping matches?
Yes — the window slides by one each step, so overlaps are reported naturally.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Hash the pattern once, then roll a fixed-width hash across the text so each window's hash updates in O(1) instead of recomputing from scratch. When a window's hash equals the pattern's hash, verify character-by-character to rule out a collision (a 'spurious hit'). Average and best case O(n + m); worst case O(n·m) if hashes collide constantly, which a good modulus and base make vanishingly unlikely.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you understand that hashing gives a fast probabilistic filter that still needs verification, and whether you can derive the O(1) rolling update with correct modular arithmetic.

Where candidates slip

Reporting a match on hash equality without verifying characters (false positive on a collision), or botching the modular subtraction so values go negative.

How to stand out

Name the spurious-hit risk explicitly, state the O(n+m) average vs O(n·m) worst case honestly, and mention double hashing as the mitigation.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Naive — Recompute Each Window	`O(n·m)`	`O(1)`	Say it first to motivate why an O(1) hash update is worth the modular-arithmetic care.	Read
2	Rolling Hash (Optimal Average Case)Optimal	`O(n + m) average, O(n·m) worst`	`O(1)`	The intended answer. Lead with the O(1) hash roll, then immediately address spurious hits and verification.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewWindow hash== pattern hash?NoYesExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Naive — Recompute Each Window

TimeO(n·m)SpaceO(1)

Say it first to motivate why an O(1) hash update is worth the modular-arithmetic care.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

For each start s from 0 to n−m, compare the window t[s..s+m-1] with p one character at a time.

2Hint 2Explore hint

Each comparison is up to m characters, and there are about n windows → n·m work.

3Hint 3Explore hint

Notice consecutive windows share m−1 characters — recomputing everything ignores that overlap.

A · Core idea

The baseline simply re-derives whether each window equals the pattern from scratch.

The literal method. Slide a start index s across the text, and at each s compare the m characters of the window with the pattern. Stop early on the first mismatch; record s if all m match.

The overlap it ignores. Window starting at s and window starting at s+1 share m−1 characters. The naive method re-reads those shared characters every step. A rolling hash captures the window in a single number so that shifting reuses almost all prior work.

Worst case. Text "aaaa...a" with pattern "aaa...ab" matches m−1 characters per window before failing — n windows × m checks ≈ n·m. At n = m = 10⁶ that's 10¹² operations, far too slow.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

t = "abcab", p = "cab"

Array state

s=2

"cab" matches the pattern

[0]

[1]

s ↓

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final result[2]

C · Code with teaching comments

Reference implementation previewimport java.util.ArrayList; import java.util.List; public class NaiveWindow { public List<Integer> search(String t, String p) {Explore the full code

solution.javaJava

Naive — Recompute Each Window — reference

2 teaching notes

1
import java.util.ArrayList;
2
import java.util.List;
3
 
4
public class NaiveWindow {
5
    public List<Integer> search(String t, String p) {
6
        List<Integer> result = new ArrayList<>();
7
        int n = t.length(), m = p.length();
8
        for (int s = 0; s + m <= n; s++) {
9
            int j = 0;
10
            // Re-reads the whole window each shift, ignoring the m−1 shared characters.
11
            while (j < m && t.charAt(s + j) == p.charAt(j)) j++;
12
            // Full match recorded.
13
            if (j == m) result.add(s);
14
        }
15
        return result;
16
    }
17
 
18
    public static void main(String[] args) {
19
        System.out.println(new NaiveWindow().search("abcab", "cab"));
20
    }
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(n·m) timeO(1) spaceOpen the invariant and proofExplore the proof

The redundancy is the m−1 overlapping characters between adjacent windows. Rabin–Karp's rolling hash is exactly a way to update the window's fingerprint in O(1) instead of rereading that overlap.

ComplexityO(n·m) time, O(1) space — Up to n−m+1 windows, each compared in up to m character checks → O(n·m). Constant extra space.

E · Edge cases and pitfalls3Looping s past n−m → out-of-bounds.Explore edge cases

Pitfalls

Looping s past n−m → out-of-bounds.
Treating it as acceptable at large n — adversarial inputs are genuinely quadratic.
Not early-exiting the inner loop on mismatch (still O(n·m) but slower constant).

03.2

Approach 2 of 2 · Optimal

Rolling Hash (Optimal Average Case)

TimeO(n + m) average, O(n·m) worstSpaceO(1)

The intended answer. Lead with the O(1) hash roll, then immediately address spurious hits and verification.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Treat a length-m string as a base-b number mod M: hash = s[0]*b^{m-1} + ... + s[m-1]. Equal strings always share this hash.

2Hint 2Explore hint

When the window slides one step right, the new hash is (old hash minus the leaving char's high-order term) times b, plus the entering char — an O(1) update if you precompute b^{m-1} mod M.

3Hint 3Explore hint

A matching hash might be a coincidence (collision). Verify the m characters before recording, and you stay correct even when hashes collide.

A · Core idea

Rabin–Karp encodes each fixed-width window as a polynomial hash and slides that hash across the text in constant time per step.

The hash as a base-b number. Read the m characters of a window as digits of a base-b number taken modulo a large prime M: hash = c0·b^{m-1} + c1·b^{m-2} + … + c_{m-1}. Two windows that are character-for-character equal always produce the same hash. Two different windows usually produce different hashes, but not always — that 'not always' is the collision you must handle.

The O(1) roll — the core trick. When the window moves from [i, i+m-1] to [i+1, i+m], you want the new hash without recomputing the sum. Subtract the outgoing character's contribution c_i · b^{m-1}, multiply the rest by b (shifting every digit up one place), then add the incoming character c_{i+m}, all mod M. Precomputing b^{m-1} mod M once makes this three arithmetic operations regardless of m.

Spurious hits and why verification is mandatory. A hash equal to the pattern's hash is a candidate, not a guarantee. Because many strings map into the same residue class mod M, two unequal windows can share a hash — a 'spurious hit'. So on every hash match, compare the actual m characters. With a large prime M and base b above the alphabet, spurious hits are rare, so verification rarely fires and the average cost stays linear. But you can never skip it without risking a wrong answer.

Modular hygiene. Subtraction can make the intermediate value negative; add M before the final mod so the stored hash stays in [0, M). In languages with fixed-width integers, also keep the base and modulus small enough that hash·b doesn't overflow (use 64-bit, or a modulus near 10⁹).

Honest complexity. Average and best case are O(n + m). The worst case is O(n·m) when hashes collide on (almost) every window — possible if an adversary engineers the input against a known fixed base/modulus. Randomizing the base or using two independent hashes (double hashing) drives the collision probability to negligible levels.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

t = "abcab", p = "cab", b = 256, M = 101

Array state

window [0,2]

hash("abc")

L ↓

[0]

[1]

R ↓

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final result[2]

C · Code with teaching comments

solution.javaJava

Rolling Hash (Optimal Average Case) — optimal

5 teaching notes

1
import java.util.ArrayList;
2
import java.util.List;
3
 
4
public class RabinKarp {
5
    private static final long BASE = 256;
6
    private static final long MOD = 1_000_000_007L;
7
 
8
    public List<Integer> search(String t, String p) {
9
        List<Integer> result = new ArrayList<>();
10
        int n = t.length(), m = p.length();
11
        if (m > n) return result;
12
 
13
        long highOrder = 1; // BASE^(m-1) mod MOD
14
        // Precompute BASE^(m-1) mod MOD once — the high-order weight removed on each
15
        // roll.
16
        for (int k = 0; k < m - 1; k++) highOrder = (highOrder * BASE) % MOD;
17
 
18
        long pHash = 0, wHash = 0;
19
        for (int k = 0; k < m; k++) {
20
            // Horner's method builds the polynomial hash digit by digit.
21
            pHash = (pHash * BASE + p.charAt(k)) % MOD;
22
            wHash = (wHash * BASE + t.charAt(k)) % MOD;
23
        }
24
 
25
        for (int i = 0; i + m <= n; i++) {
26
            // Hash equality is only a candidate; matches(...) verifies characters to
27
            // reject spurious hits.
28
            if (wHash == pHash && matches(t, i, p)) {
29
                result.add(i);
30
            }
31
            if (i + m < n) {
32
                // Remove the outgoing char's contribution; + MOD keeps the value
33
                // non-negative after subtraction.
34
                wHash = (wHash - t.charAt(i) * highOrder % MOD + MOD) % MOD;
35
                // Shift remaining digits up and add the incoming char — the O(1) roll.
36
                wHash = (wHash * BASE + t.charAt(i + m)) % MOD;
37
            }
38
        }
39
        return result;
40
    }
41
 
42
    private boolean matches(String t, int start, String p) {
43
        for (int k = 0; k < p.length(); k++) {
44
            if (t.charAt(start + k) != p.charAt(k)) return false;
45
        }
46
        return true;
47
    }
48
 
49
    public static void main(String[] args) {
50
        System.out.println(new RabinKarp().search("abedabcabc", "abc"));
51
    }
52
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.52 lines

D · Why it works and complexityO(n + m) average, O(n·m) worst timeO(1) spaceOpen the invariant and proofExplore the proof

A polynomial hash makes 'are these two length-m strings equal?' an O(1) question, and the rolling update makes 'advance the window' O(1) too. The price is that equality becomes probabilistic — so you bolt on a cheap O(m) verification that runs only on the rare hash match, recovering exactness without losing the average-case speed.

ComplexityO(n + m) average, O(n·m) worst time, O(1) space — Computing the pattern hash and the first window hash is O(m). Each of the ~n rolls is O(1). Verifications are O(m) but happen only on hash matches, which are rare with a good modulus → O(n + m) expected. If every window collides (adversarial), every verification costs O(m) → O(n·m) worst case.

E · Edge cases and pitfalls7t = "aaaaa", p = "aa" — Adjacent windows all hash equal and verify → overlapping matches [0,1,2,3].Explore edge cases

Edge cases handled

t = "aaaaa", p = "aa"Adjacent windows all hash equal and verify → overlapping matches [0,1,2,3].
p longer than tEarly return empty before hashing.
engineered collisionsVerification still keeps the answer correct; only the time degrades toward O(n·m). Double hashing mitigates.

Pitfalls

Reporting a match on hash equality without verifying characters — wrong on collisions.
Letting the rolling hash go negative after subtraction — add MOD before the final mod (matters in Java).
Integer overflow when MOD·BASE exceeds the type — use 64-bit and a modulus near 10⁹.
Using a tiny modulus 'to keep numbers small' — collisions become frequent and you drift toward O(n·m).

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewimport java.util.ArrayList; import java.util.List; public class RabinKarp { private static final long BASE = 256;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

import java.util.ArrayList;
import java.util.List;

public class RabinKarp {
    private static final long BASE = 256;
    private static final long MOD = 1_000_000_007L;

public List<Integer> search(String t, String p) {
        List<Integer> result = new ArrayList<>();
        int n = t.length(), m = p.length();
        if (m > n) return result;

long highOrder = 1; // BASE^(m-1) mod MOD
        for (int k = 0; k < m - 1; k++) highOrder = (highOrder * BASE) % MOD;

long pHash = 0, wHash = 0;
        for (int k = 0; k < m; k++) {
            pHash = (pHash * BASE + p.charAt(k)) % MOD;
            wHash = (wHash * BASE + t.charAt(k)) % MOD;
        }

for (int i = 0; i + m <= n; i++) {
            if (wHash == pHash && matches(t, i, p)) {
                result.add(i);
            }
            if (i + m < n) {
                wHash = (wHash - t.charAt(i) * highOrder % MOD + MOD) % MOD;
                wHash = (wHash * BASE + t.charAt(i + m)) % MOD;
            }
        }
        return result;
    }

private boolean matches(String t, int start, String p) {
        for (int k = 0; k < p.length(); k++) {
            if (t.charAt(start + k) != p.charAt(k)) return false;
        }
        return true;
    }

public static void main(String[] args) {
        System.out.println(new RabinKarp().search("abedabcabc", "abc"));
    }
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

No verification after a hash match

Different strings can share a hash (spurious hit). Reporting on hash equality alone returns wrong indices whenever a collision occurs.

Explore the code comparison

Don't write this

if w_hash == p_hash:
    result.append(i)   # WRONG: collision => false positive

Write this instead

if w_hash == p_hash and t[i:i + m] == p:
    result.append(i)

Negative hash after the roll

In fixed-width-int languages, subtracting the outgoing term can make the hash negative, corrupting later comparisons. Add MOD before taking mod again.

Explore the code comparison

Don't write this

wHash = (wHash - t.charAt(i) * highOrder % MOD) % MOD; // may be negative

Write this instead

wHash = (wHash - t.charAt(i) * highOrder % MOD + MOD) % MOD;

Modulus too small

A small M means many strings collide, so verification fires constantly and the algorithm slides toward its O(n·m) worst case while also risking overflow-free but useless hashes.

Explore the code comparison

Don't write this

MOD = 101   # collisions everywhere

Write this instead

MOD = 1_000_000_007   # large prime keeps spurious hits rare

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Rolling polynomial hash over a sliding fixed-width window

Code pattern to memorize

hash(s[0..m-1]) = (s[0]*b^{m-1} + s[1]*b^{m-2} + ... + s[m-1]) mod M
roll forward by one:
    h = ( (h - s[i]*b^{m-1}) * b + s[i+m] ) mod M   (keep non-negative)
on hash match: VERIFY characters before reporting

Rules to remember

1A hash match is necessary, not sufficient — always verify characters to reject spurious hits.
2Precompute b^{m-1} mod M once; the roll uses it to subtract the outgoing character's contribution.
3Pick a large prime modulus M and a base b larger than the alphabet to keep collisions rare.
4Take mod after every operation and add M before another mod to keep values non-negative (Java/Python int overflow vs negative quirks differ).
5Worst case is O(n·m) under adversarial collisions — say this out loud; double-hashing makes it astronomically unlikely.

Use this pattern when

Substring search where average-case linear time is acceptable
Comparing many equal-length substrings (precomputed hashes give O(1) equality checks)
Detecting duplicate substrings of a fixed length (e.g. Repeated DNA Sequences)
Plagiarism / fingerprinting style problems over sliding windows

Choose another pattern when

You need a guaranteed worst-case linear bound → KMP or Z-algorithm
Multiple patterns at once → Aho–Corasick
Tiny inputs where built-in find suffices → don't hand-roll hashing
Adversary controls the input and can engineer collisions → randomize base or use double hashing, or switch to KMP

Interview takeaway

Rabin–Karp trades exactness for speed: a rolling hash compares windows in O(1), and a cheap verification step restores correctness whenever hashes happen to collide. It's the gateway to every rolling-hash / string-fingerprint technique.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternRolling Hash / String Fingerprinting. Recognise it whenever you slide a fixed-width window and need fast equality: substring search, duplicate-substring detection, and longest-duplicate-via-binary-search all ride on the O(1) rolling update plus verification.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Repeated DNA Sequences
Coming soon
Roll a fixed-length (10) hash and bucket windows to find sequences appearing more than once.
Longest Duplicate Substring
Coming soon
Binary search the length, use rolling hashes (double-hashed) to test for a repeated substring of that length.
Find All Anagram Hashes
Coming soon
Use a frequency-based rolling signature instead of a positional polynomial hash.
KMP / Z (guaranteed worst case)
When you must avoid the O(n·m) collision worst case entirely, switch to a comparison-based linear matcher.

Same pattern

←

Pattern Search — Z-Algorithm

Continue · Next problem

2D Array - DS

mediumStringsSometimes asked

Rabin–Karp Substring Search (Rolling Hash)

Arrays & Hashing · 41 of 83 · 12 min

Given a text t of length n and a pattern p of length m, return all starting indices in t where p occurs, using a rolling hash.

Report overlapping occurrences. Your hash equality must be confirmed by an actual character comparison so that a hash collision never produces a wrong answer.

In plain English

Examples

Example 1

Input: t = "abedabcabc", p = "abc"
Output: [4, 7]
Note: Windows at 4 and 7 hash equal to p and verify as "abc". Any other coincidental hash matches are rejected by verification.

Example 2

Input: t = "aaaaa", p = "aa"
Output: [0, 1, 2, 3]
Note: Overlapping matches; each adjacent window hashes equal and verifies.

Example 3

Input: t = "abc", p = "d"
Output: []
Note: No window hash equals p's hash; empty result.

Constraints

1 ≤ m ≤ n ≤ 10⁶
Strings are ASCII; treat each character's code as its numeric value
Use a large prime modulus to keep collision probability low
Report overlapping occurrences

Clarifying questions4First question: Do I have to handle hash collisions?Explore questions

Q1.Do I have to handle hash collisions?
Yes. A matching hash is only a candidate; verify the characters. Skipping verification is a correctness bug, not an optimization.
Q2.What modulus and base should I use?
A large prime modulus (e.g. ~10⁹+7) and a base above the alphabet size (e.g. 256 or a random prime). Larger and randomized → fewer collisions.
Q3.Is worst-case O(n·m) acceptable?
Average case is O(n+m); worst case degrades only under pathological collisions. If a guaranteed bound is required, use KMP instead.
Q4.Overlapping matches?
Yes — the window slides by one each step, so overlaps are reported naturally.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you understand that hashing gives a fast probabilistic filter that still needs verification, and whether you can derive the O(1) rolling update with correct modular arithmetic.

Where candidates slip

Reporting a match on hash equality without verifying characters (false positive on a collision), or botching the modular subtraction so values go negative.

How to stand out

Name the spurious-hit risk explicitly, state the O(n+m) average vs O(n·m) worst case honestly, and mention double hashing as the mitigation.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Naive — Recompute Each Window	`O(n·m)`	`O(1)`	Say it first to motivate why an O(1) hash update is worth the modular-arithmetic care.	Read
2	Rolling Hash (Optimal Average Case)Optimal	`O(n + m) average, O(n·m) worst`	`O(1)`	The intended answer. Lead with the O(1) hash roll, then immediately address spurious hits and verification.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Naive — Recompute Each Window

TimeO(n·m)SpaceO(1)

Say it first to motivate why an O(1) hash update is worth the modular-arithmetic care.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

For each start s from 0 to n−m, compare the window t[s..s+m-1] with p one character at a time.

2Hint 2Explore hint

Each comparison is up to m characters, and there are about n windows → n·m work.

3Hint 3Explore hint

Notice consecutive windows share m−1 characters — recomputing everything ignores that overlap.

A · Core idea

The baseline simply re-derives whether each window equals the pattern from scratch.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

t = "abcab", p = "cab"

Array state

s=2

"cab" matches the pattern

[0]

[1]

s ↓

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final result[2]

C · Code with teaching comments

Reference implementation previewimport java.util.ArrayList; import java.util.List; public class NaiveWindow { public List<Integer> search(String t, String p) {Explore the full code

solution.javaJava

Naive — Recompute Each Window — reference

2 teaching notes

1
import java.util.ArrayList;
2
import java.util.List;
3
 
4
public class NaiveWindow {
5
    public List<Integer> search(String t, String p) {
6
        List<Integer> result = new ArrayList<>();
7
        int n = t.length(), m = p.length();
8
        for (int s = 0; s + m <= n; s++) {
9
            int j = 0;
10
            // Re-reads the whole window each shift, ignoring the m−1 shared characters.
11
            while (j < m && t.charAt(s + j) == p.charAt(j)) j++;
12
            // Full match recorded.
13
            if (j == m) result.add(s);
14
        }
15
        return result;
16
    }
17
 
18
    public static void main(String[] args) {
19
        System.out.println(new NaiveWindow().search("abcab", "cab"));
20
    }
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(n·m) timeO(1) spaceOpen the invariant and proofExplore the proof

The redundancy is the m−1 overlapping characters between adjacent windows. Rabin–Karp's rolling hash is exactly a way to update the window's fingerprint in O(1) instead of rereading that overlap.

ComplexityO(n·m) time, O(1) space — Up to n−m+1 windows, each compared in up to m character checks → O(n·m). Constant extra space.

E · Edge cases and pitfalls3Looping s past n−m → out-of-bounds.Explore edge cases

Pitfalls

Looping s past n−m → out-of-bounds.
Treating it as acceptable at large n — adversarial inputs are genuinely quadratic.
Not early-exiting the inner loop on mismatch (still O(n·m) but slower constant).

03.2

Approach 2 of 2 · Optimal

Rolling Hash (Optimal Average Case)

TimeO(n + m) average, O(n·m) worstSpaceO(1)

The intended answer. Lead with the O(1) hash roll, then immediately address spurious hits and verification.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Treat a length-m string as a base-b number mod M: hash = s[0]*b^{m-1} + ... + s[m-1]. Equal strings always share this hash.

2Hint 2Explore hint

When the window slides one step right, the new hash is (old hash minus the leaving char's high-order term) times b, plus the entering char — an O(1) update if you precompute b^{m-1} mod M.

3Hint 3Explore hint

A matching hash might be a coincidence (collision). Verify the m characters before recording, and you stay correct even when hashes collide.

A · Core idea

Rabin–Karp encodes each fixed-width window as a polynomial hash and slides that hash across the text in constant time per step.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

t = "abcab", p = "cab", b = 256, M = 101

Array state

window [0,2]

hash("abc")

L ↓

[0]

[1]

R ↓

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final result[2]

C · Code with teaching comments

solution.javaJava

Rolling Hash (Optimal Average Case) — optimal

5 teaching notes

1
import java.util.ArrayList;
2
import java.util.List;
3
 
4
public class RabinKarp {
5
    private static final long BASE = 256;
6
    private static final long MOD = 1_000_000_007L;
7
 
8
    public List<Integer> search(String t, String p) {
9
        List<Integer> result = new ArrayList<>();
10
        int n = t.length(), m = p.length();
11
        if (m > n) return result;
12
 
13
        long highOrder = 1; // BASE^(m-1) mod MOD
14
        // Precompute BASE^(m-1) mod MOD once — the high-order weight removed on each
15
        // roll.
16
        for (int k = 0; k < m - 1; k++) highOrder = (highOrder * BASE) % MOD;
17
 
18
        long pHash = 0, wHash = 0;
19
        for (int k = 0; k < m; k++) {
20
            // Horner's method builds the polynomial hash digit by digit.
21
            pHash = (pHash * BASE + p.charAt(k)) % MOD;
22
            wHash = (wHash * BASE + t.charAt(k)) % MOD;
23
        }
24
 
25
        for (int i = 0; i + m <= n; i++) {
26
            // Hash equality is only a candidate; matches(...) verifies characters to
27
            // reject spurious hits.
28
            if (wHash == pHash && matches(t, i, p)) {
29
                result.add(i);
30
            }
31
            if (i + m < n) {
32
                // Remove the outgoing char's contribution; + MOD keeps the value
33
                // non-negative after subtraction.
34
                wHash = (wHash - t.charAt(i) * highOrder % MOD + MOD) % MOD;
35
                // Shift remaining digits up and add the incoming char — the O(1) roll.
36
                wHash = (wHash * BASE + t.charAt(i + m)) % MOD;
37
            }
38
        }
39
        return result;
40
    }
41
 
42
    private boolean matches(String t, int start, String p) {
43
        for (int k = 0; k < p.length(); k++) {
44
            if (t.charAt(start + k) != p.charAt(k)) return false;
45
        }
46
        return true;
47
    }
48
 
49
    public static void main(String[] args) {
50
        System.out.println(new RabinKarp().search("abedabcabc", "abc"));
51
    }
52
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.52 lines

D · Why it works and complexityO(n + m) average, O(n·m) worst timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7t = "aaaaa", p = "aa" — Adjacent windows all hash equal and verify → overlapping matches [0,1,2,3].Explore edge cases

Edge cases handled

t = "aaaaa", p = "aa"Adjacent windows all hash equal and verify → overlapping matches [0,1,2,3].
p longer than tEarly return empty before hashing.
engineered collisionsVerification still keeps the answer correct; only the time degrades toward O(n·m). Double hashing mitigates.

Pitfalls

Reporting a match on hash equality without verifying characters — wrong on collisions.
Letting the rolling hash go negative after subtraction — add MOD before the final mod (matters in Java).
Integer overflow when MOD·BASE exceeds the type — use 64-bit and a modulus near 10⁹.
Using a tiny modulus 'to keep numbers small' — collisions become frequent and you drift toward O(n·m).

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewimport java.util.ArrayList; import java.util.List; public class RabinKarp { private static final long BASE = 256;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

import java.util.ArrayList;
import java.util.List;

public class RabinKarp {
    private static final long BASE = 256;
    private static final long MOD = 1_000_000_007L;

public List<Integer> search(String t, String p) {
        List<Integer> result = new ArrayList<>();
        int n = t.length(), m = p.length();
        if (m > n) return result;

long highOrder = 1; // BASE^(m-1) mod MOD
        for (int k = 0; k < m - 1; k++) highOrder = (highOrder * BASE) % MOD;

long pHash = 0, wHash = 0;
        for (int k = 0; k < m; k++) {
            pHash = (pHash * BASE + p.charAt(k)) % MOD;
            wHash = (wHash * BASE + t.charAt(k)) % MOD;
        }

public static void main(String[] args) {
        System.out.println(new RabinKarp().search("abedabcabc", "abc"));
    }
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

No verification after a hash match

Different strings can share a hash (spurious hit). Reporting on hash equality alone returns wrong indices whenever a collision occurs.

Explore the code comparison

Don't write this

if w_hash == p_hash:
    result.append(i)   # WRONG: collision => false positive

Write this instead

if w_hash == p_hash and t[i:i + m] == p:
    result.append(i)

Negative hash after the roll

In fixed-width-int languages, subtracting the outgoing term can make the hash negative, corrupting later comparisons. Add MOD before taking mod again.

Explore the code comparison

Don't write this

wHash = (wHash - t.charAt(i) * highOrder % MOD) % MOD; // may be negative

Write this instead

wHash = (wHash - t.charAt(i) * highOrder % MOD + MOD) % MOD;

Modulus too small

A small M means many strings collide, so verification fires constantly and the algorithm slides toward its O(n·m) worst case while also risking overflow-free but useless hashes.

Explore the code comparison

Don't write this

MOD = 101   # collisions everywhere

Write this instead

MOD = 1_000_000_007   # large prime keeps spurious hits rare

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Rolling polynomial hash over a sliding fixed-width window

Code pattern to memorize

hash(s[0..m-1]) = (s[0]*b^{m-1} + s[1]*b^{m-2} + ... + s[m-1]) mod M
roll forward by one:
    h = ( (h - s[i]*b^{m-1}) * b + s[i+m] ) mod M   (keep non-negative)
on hash match: VERIFY characters before reporting

Rules to remember

1A hash match is necessary, not sufficient — always verify characters to reject spurious hits.
2Precompute b^{m-1} mod M once; the roll uses it to subtract the outgoing character's contribution.
3Pick a large prime modulus M and a base b larger than the alphabet to keep collisions rare.
4Take mod after every operation and add M before another mod to keep values non-negative (Java/Python int overflow vs negative quirks differ).
5Worst case is O(n·m) under adversarial collisions — say this out loud; double-hashing makes it astronomically unlikely.

Use this pattern when

Substring search where average-case linear time is acceptable
Comparing many equal-length substrings (precomputed hashes give O(1) equality checks)
Detecting duplicate substrings of a fixed length (e.g. Repeated DNA Sequences)
Plagiarism / fingerprinting style problems over sliding windows

Choose another pattern when

You need a guaranteed worst-case linear bound → KMP or Z-algorithm
Multiple patterns at once → Aho–Corasick
Tiny inputs where built-in find suffices → don't hand-roll hashing
Adversary controls the input and can engineer collisions → randomize base or use double hashing, or switch to KMP

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Repeated DNA Sequences
Coming soon
Roll a fixed-length (10) hash and bucket windows to find sequences appearing more than once.
Longest Duplicate Substring
Coming soon
Binary search the length, use rolling hashes (double-hashed) to test for a repeated substring of that length.
Find All Anagram Hashes
Coming soon
Use a frequency-based rolling signature instead of a positional polynomial hash.
KMP / Z (guaranteed worst case)
When you must avoid the O(n·m) collision worst case entirely, switch to a comparison-based linear matcher.

Same pattern

←

Pattern Search — Z-Algorithm

Continue · Next problem

2D Array - DS