What the hash is
Rabin-Karp treats each window of length m as a number written in base B, reduced modulo a prime P:
H(s[i..i+m-1]) = (s[i]·B^(m-1) + s[i+1]·B^(m-2) + ... + s[i+m-1]) mod P
Derive the slide from that definition rather than reciting it. Moving the window one step right removes the leftmost term, s[i]·B^(m-1), multiplies what is left by B so every remaining term moves up one power, and adds the new character as the units term:
H(i+1) = ((H(i) - s[i]·B^(m-1))·B + s[i+m]) mod P
Precompute B^(m-1) mod P once. Each slide is then a constant number of multiplications and reductions, so the rolling hash for all n − m + 1 windows costs O(n) in total, plus O(m) to hash the pattern and the first window.
The code, and the two arithmetic traps in it
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ThreadLocalRandom;
final class RabinKarp {
static List<Integer> findAll(String text, String pattern) {
final long P = 1_000_000_007L;
final long B = ThreadLocalRandom.current().nextLong(256, P);
int n = text.length(), m = pattern.length();
List<Integer> hits = new ArrayList<>();
if (m == 0 || m > n) return hits;
long high = 1;
for (int i = 1; i < m; i++) high = high * B % P;
long hp = 0, hw = 0;
for (int i = 0; i < m; i++) {
hp = (hp * B + pattern.charAt(i)) % P;
hw = (hw * B + text.charAt(i)) % P;
}
( ; ; i++) {
(hw == hp && text.regionMatches(i, pattern, , m)) hits.add(i);
(i + m == n) ;
hw = (hw - text.charAt(i) * high % P + P) % P;
hw = (hw * B + text.charAt(i + m)) % P;
}
hits;
}
}
The first trap is the sign. Java's % keeps the sign of the left operand, so hw - text.charAt(i) * high % P is negative whenever the removed term is larger than what remains. A negative hash will never equal the pattern's, and matches silently vanish. Adding P before the final reduction fixes it.
The second is overflow. Every stored hash is below P, so hw * B and high * B are below P squared, about 10^18, under Long.MAX_VALUE of roughly 9.2 × 10^18. A character is at most 65,535, so charAt(i) * high is far smaller still. Choose a prime near 2^62 instead and those products overflow without any error.
Equal hashes are a candidate, not a match
This is the question the interviewer is really asking. Hashing maps many strings to one value, so two different windows can share the pattern's hash. What that costs depends on whether you verify.
Without verification, a collision is a wrong answer. The algorithm becomes a Monte Carlo one: fast, and occasionally reports a match that is not there. You can bound how often. With a base drawn at random, two different strings of length m collide with probability of roughly (m − 1)/P at most, because their hash difference is a non-zero polynomial in B of degree below m, and such a polynomial has at most m − 1 roots modulo a prime.
Now apply the union bound across every window. With a text of a million characters, a thousand-character pattern and P near 10^9, you get 10^6 × 999 / 10^9, which is about 1. That bound promises nothing. Two independent bases multiply the two probabilities, which is why "double hashing" is the usual answer when verification is too expensive.
With verification, a collision costs time instead. The answer is always correct, which makes it a Las Vegas algorithm. Each spurious candidate costs up to m character comparisons. A handful of them cost nothing. But if an adversary knows your base and modulus, they can build a text where the collisions keep coming, and the run slides towards O(nm).
Why the base must be random
A fixed, public base is what lets the adversary in. Java's own String.hashCode is a polynomial hash with base 31, and "Aa" and "BB" both come to exactly 2112 before any reduction, so they collide under base 31 whatever modulus you pick. Concatenating such blocks, as in "AaBB" and "BBAa", gives as many colliding strings as anyone wants.
Letting a long overflow, which works modulo 2^64, is no safer. With an even base, B^64 is zero modulo 2^64, so only the last 64 characters of a window affect its hash. With an odd base, a known construction from the Thue–Morse sequence still produces collisions.
Choosing B at random for each run, as above, takes the input out of the adversary's control. The (m − 1)/P bound then holds whatever text they supply, provided they cannot observe the base.
Quadratic with no collision at all
Name this input before the interviewer does. Search for aaaa in a text of a million a characters. Every window genuinely matches, so every window is verified, at four comparisons each. Scale the pattern to a thousand as and every one of roughly a million windows costs a thousand comparisons. That is O(nm), with zero collisions, and it is why a precise statement of the bound is O(n + m) expected time plus m per reported or spurious candidate.
If the interviewer wants linear time guaranteed rather than expected, Rabin-Karp is the wrong tool. KMP's failure table gives O(n + m) on every input, and the KMP question covers it. Rabin-Karp earns its place elsewhere: one pass can test each window against a set of hashes for many same-length patterns, and the same rolling hash solves substring-equality problems such as the longest repeated substring.
A Rabin-Karp hash match nominates a window; it never proves one. Verify every candidate and pick the base at random, and a collision costs you comparisons instead of correctness.
© 2026 Preptima. Originally published at preptima.com (opens in a new tab).