A SKU checker holds a set of banned prefixes, each length m, and must scan a warehouse line of length n. Running KMP once per prefix is k linear scans. Hashing each window of m characters from scratch is O(n · m). The line is already a char[]. The job is “does this window look like any needle,” not “rebuild the fingerprint from zero.”
Rabin-Karp hashes the current window, then rolls: drop the leaving character, add the entering one, in O(1). Equal hashes are a candidate. Character equality is the proof. Collisions are expected; they are not a bug if you verify.
This post is that roll and that verify. The LPS automaton is KMP. Skip-from-the-end is Boyer-Moore. A dictionary of many variable-length needles is Aho-Corasick. Families live on the Algorithms Roadmap.
Hash the window, do not re-sum it
A polynomial rolling hash treats the window as a base-R number:
h = t[i]·R^{m-1} + t[i+1]·R^{m-2} + … + t[i+m-1]·R^0 (mod Q)Slide one step:
h' = (h - t[i]·R^{m-1}) · R + t[i+m] (mod Q)One multiply, one subtract, one add. Precompute R^{m-1} mod Q so the drop is O(1).
static final long R = 256;
static final long Q = 1_000_000_007L;
static long powRm1(int m) {
long p = 1;
for (int i = 1; i < m; i++) {
p = (p * R) % Q;
}
return p;
}
static long hash(char[] s, int from, int m, long rm1) {
long h = 0;
for (int i = 0; i < m; i++) {
h = (h * R + s[from + i]) % Q;
}
return h;
}rm1 is unused in hash of a fresh window; it is the drop factor in the roll. Keep it beside the scanner.
Modulus arithmetic must stay non-negative. Java % on a negative left-hand side is negative. After subtract, add Q before the next %.
One needle: roll, compare, verify
static int indexOfRabinKarp(String text, String pattern) {
int n = text.length();
int m = pattern.length();
if (m == 0) {
return 0;
}
if (m > n) {
return -1;
}
char[] t = text.toCharArray();
char[] p = pattern.toCharArray();
long rm1 = powRm1(m);
long ph = 0;
long th = 0;
for (int i = 0; i < m; i++) {
ph = (ph * R + p[i]) % Q;
th = (th * R + t[i]) % Q;
}
for (int i = 0; i + m <= n; i++) {
if (th == ph && matches(t, i, p)) {
return i;
}
if (i + m < n) {
th = (th - (t[i] * rm1) % Q + Q) % Q;
th = (th * R + t[i + m]) % Q;
}
}
return -1;
}
static boolean matches(char[] t, int i, char[] p) {
for (int j = 0; j < p.length; j++) {
if (t[i + j] != p[j]) {
return false;
}
}
return true;
}Average time is O(n + m) when collisions are rare. Worst case — a hostile modulus and a family of colliding windows — falls back to O(n · m) because every window verifies. That is why you still write matches. Skipping the character check is how you ship a false hit.
Note: A second hash (double hashing) cuts accidental collisions. It does not remove the verify if you need a proof, not a sketch.
Many needles of the same length
Store pattern hashes in a HashSet<Long>. Roll the text once. On a set hit, verify against the patterns that share that hash (a Map<Long, List<String>>).
static boolean containsAny(String text, List<String> patterns) {
if (patterns.isEmpty()) {
return false;
}
int m = patterns.getFirst().length();
int n = text.length();
if (m > n) {
return false;
}
Map<Long, List<String>> byHash = new HashMap<>();
for (String p : patterns) {
if (p.length() != m) {
throw new IllegalArgumentException("same length only");
}
long h = 0;
for (int i = 0; i < m; i++) {
h = (h * R + p.charAt(i)) % Q;
}
byHash.computeIfAbsent(h, k -> new ArrayList<>()).add(p);
}
char[] t = text.toCharArray();
long rm1 = powRm1(m);
long th = 0;
for (int i = 0; i < m; i++) {
th = (th * R + t[i]) % Q;
}
for (int i = 0; i + m <= n; i++) {
List<String> cand = byHash.get(th);
if (cand != null) {
for (String p : cand) {
if (matches(t, i, p.toCharArray())) {
return true;
}
}
}
if (i + m < n) {
th = (th - (t[i] * rm1) % Q + Q) % Q;
th = (th * R + t[i + m]) % Q;
}
}
return false;
}Same-length is the Rabin-Karp sweet spot. Mixed lengths need one roll per m, or Aho-Corasick.
When not to use Rabin-Karp
- One needle, you already own LPS. KMP is worst-case linear without a modulus story.
- Needles of many lengths, one pass. Aho-Corasick.
- You treated the hash as equality. That is a Bloom-filter mistake on strings. Verify.
- Cryptographic identity. This polynomial hash is not SHA. Do not use it as a checksum of a file.
Cheat sheet
Job: exact match via window hash, then verify
Roll: drop leftmost · R^{m-1}, ×R, add new (mod Q)
Collision: expected; matches() is the proof
Many: HashSet of pattern hashes; same m
Time: average O(n+m); worst O(n·m) if every window collides
JDK: no RabinKarp type; long + % ; String.indexOf for one needle
Not this: KMP worst-case linear; Aho-Corasick mixed lengthsDo:
- Keep
Qa 32-or-64-bit prime; keep the drop factorR^{m-1} mod Q. - Verify characters on every hash hit.
- Use a map of hash → patterns when
kneedles sharem.
Don’t:
- Return on hash equality without a character check.
- Let
(th - drop)go negative without+ Q. - Quote average
O(n)as a guarantee against an adversary.
Wrap-up
Rabin-Karp is a rolling fingerprint: one multiply to slide the window, a hash compare to cheaply reject, and a character compare to confirm. It earns its keep when many same-length needles share one haystack scan. It is not a substitute for KMP’s worst-case bound, and it is not a crypto hash.
The layout was already a string. The procedure is the roll. When the mismatch is usually at the end of the window, the next skip table is Boyer-Moore.