☕ DSA Java Articles

Topics › Strings › Hard String Problems

Rabin Karp Algorithm

Hard TUF ID 979 A2ZSDE

Java source ↗ Edit this article ↗

Problem

Given a string text of length n and a string pattern of length m, return every index i (0-based, in increasing order) such that text[i..i+m) equals pattern. Occurrences may overlap. Use the Rabin-Karp algorithm, which finds candidate positions by comparing hashes instead of characters.

Constraints: 1 ≤ m, 0 ≤ n ≤ 10^5. If the pattern is longer than the text there are no occurrences; the Java file also returns an empty list for an empty pattern, a convention worth stating explicitly in an interview.

Example 1

text = "abracadabra", pattern = "abra"
answer = [0, 7]           // "abra" starts at index 0 and at index 7

Example 2

text = "aaaaa", pattern = "aa"
answer = [0, 1, 2, 3]     // overlapping occurrences all count

Example 3

text = "abc", pattern = "d"
answer = []

Approach 1: Brute force

Intuition. Line the pattern up under every possible starting position of the text and compare character by character until a mismatch or a full match. There are n - m + 1 starting positions, and each comparison can take up to m steps.

Algorithm.

  1. For each i from 0 while i + m ≤ n:
  2. Advance k while k < m and text[i + k] == pattern[k].
  3. If k == m, record i.
static List<Integer> bruteForce(String text, String pattern) {
    List<Integer> res = new ArrayList<>();
    int n = text.length(), m = pattern.length();
    if (m == 0) return res;
    for (int i = 0; i + m <= n; i++) {
        int k = 0;
        while (k < m && text.charAt(i + k) == pattern.charAt(k)) k++;
        if (k == m) res.add(i);
    }
    return res;
}

Complexity. Time O(n · m) in the worst case, for example text = "aaaa...a" and pattern = "aa...ab", where every alignment matches almost all of the pattern before failing. Space O(1) beyond the output.

The waste is that neighbouring windows share m - 1 characters, yet each comparison starts from nothing.

Approach 2: Optimal, Rabin-Karp with a rolling hash

Intuition. Give every string of length m a fingerprint, a number computed from its characters, such that equal strings always have equal fingerprints. Compute the pattern’s fingerprint once. Then compute the fingerprint of every window of the text. Where the fingerprints differ, the window certainly does not match, and we skip it in O(1). Where they agree, the window very probably matches, and a character comparison confirms it.

That only helps if the window fingerprints are cheap. The polynomial hash makes them cheap, because it treats the window as an m-digit number in base B:

hash(w) = (w[0]·B^(m-1) + w[1]·B^(m-2) + ... + w[m-1]) mod M

Sliding the window one step right is then like changing a number on an odometer: subtract the leading digit times its weight B^(m-1), multiply by B to shift, and add the new last digit. That is three arithmetic operations, regardless of m. This is the rolling hash.

The base B = 256 covers ASCII characters, and the prime modulus M = 10^9 + 7 keeps every intermediate product inside a long.

static final long MOD = 1_000_000_007L;
static final long BASE = 256;

Algorithm.

  1. If m == 0 or m > n, return an empty list.
  2. Compute high = B^(m-1) mod M, the weight of a window’s first character.
  3. Compute hp, the hash of the pattern, and hw, the hash of text[0..m), with Horner’s rule.
  4. For each window start i:
    • If hw == hp and the window really equals the pattern, record i.
    • Stop after the last window. Otherwise roll: remove text[i]·high, multiply by B, add text[i + m].
static List<Integer> rabinKarp(String text, String pattern) {
    List<Integer> res = new ArrayList<>();
    int n = text.length(), m = pattern.length();
    if (m == 0 || m > n) return res;
    long high = 1;                                   // BASE^(m-1): weight of the window's first char
    for (int i = 1; i < m; i++) high = high * BASE % MOD;
    long hp = 0, hw = 0;                             // hash of pattern, hash of current window
    for (int i = 0; i < m; i++) {
        hp = (hp * BASE + pattern.charAt(i)) % MOD;
        hw = (hw * BASE + text.charAt(i)) % MOD;
    }
    for (int i = 0; ; i++) {
        if (hw == hp && text.regionMatches(i, pattern, 0, m)) res.add(i);   // verify: hashes can collide
        if (i + m == n) break;
        hw = (hw - text.charAt(i) * high % MOD + MOD) % MOD;               // remove text[i]
        hw = (hw * BASE + text.charAt(i + m)) % MOD;                        // append text[i + m]
    }
    return res;
}

Dry run with toy numbers so the arithmetic is visible: B = 10, no modulus, letter values a = 1, b = 2, c = 3, text = "abcab", pattern = "ab". The pattern hash is 12 and high = 10.

i window rolling step hash equal to 12?
0 ab initial 12 yes, verify, record 0
1 bc (12 - 1·10)·10 + 3 23 no
2 ca (23 - 2·10)·10 + 1 31 no
3 ab (31 - 3·10)·10 + 2 12 yes, verify, record 3

Why verification matters. The modulus squeezes all strings into M values, so two different strings can share a hash (a collision). Without the regionMatches check, a collision would be reported as a match. With the check, the answer is always exact, and collisions only cost time. With M ≈ 10^9 they are rare enough that the check almost always runs only on real matches.

Complexity.

Edge cases and pitfalls