Rabin Karp Algo

The problem, simply

You get a long text of length n and a short pattern of length m. Give back every index where the pattern starts in the text.

Rabin Karp turns every piece of m letters into a number, its fingerprint (a hash). Comparing two numbers is one step. Only when the numbers are equal do we read the letters to make sure.

A story to remember it

Picture it

Examples

Way 1: the simple way

Slide the pattern along the text and compare letter by letter at every start.

import java.util.*;

class Solution {
    public List<Integer> search(String text, String pattern) {
        List<Integer> found = new ArrayList<>();
        int n = text.length(), m = pattern.length();
        for (int s = 0; s + m <= n; s++) {
            int k = 0;
            while (k < m && text.charAt(s + k) == pattern.charAt(k)) k++;
            if (k == m) found.add(s);
        }
        return found;
    }
}

How long it takes: up to m letter checks at each of about n starts, O(n * m). Extra room: O(1).

Way 2: the clever way

Read a window of letters as one big number, the way 3, 0, 7 reads as 307. Letters are numbers too (A is 65), and instead of base 10 we use base d = 256. The number gets huge, so we only keep its remainder after dividing by a prime q = 101. That remainder, from 0 to 100, is the fingerprint.

To slide one step, we do not start over:

1. Take out the old first letter: subtract old * h, where h = d^(m-1) mod q is its place value.
2. Shift everything one place: multiply by d.
3. Add the new last letter.
4. Keep the remainder mod q after each step.

When the window's fingerprint equals the pattern's, read the letters to be sure. If they differ, it was a collision, a false alarm.

import java.util.*;

class Solution {
    static final int D = 256;   // how many different letters
    static final int Q = 101;   // a prime to keep the numbers small

    public List<Integer> search(String text, String pattern) {
        List<Integer> found = new ArrayList<>();
        int n = text.length(), m = pattern.length();
        if (m == 0 || m > n) return found;

        int h = 1;                                   // place value of the first letter
        for (int i = 0; i < m - 1; i++) h = h * D % Q;

        int ph = 0, th = 0;                          // pattern and window fingerprints
        for (int i = 0; i < m; i++) {
            ph = (D * ph + pattern.charAt(i)) % Q;
            th = (D * th + text.charAt(i)) % Q;
        }

        for (int i = 0; i + m <= n; i++) {
            if (ph == th && text.regionMatches(i, pattern, 0, m)) {
                found.add(i);                        // same fingerprint and same letters
            }
            if (i + m < n) {                         // roll to the next window
                th = (th - text.charAt(i) * h % Q + Q) % Q;   // take out the old letter
                th = (th * D + text.charAt(i + m)) % Q;       // shift and add the new one
            }
        }
        return found;
    }
}

How long it takes: O(m) to build the first fingerprints, then O(1) to roll each of the n windows. A letter check costs m, but it only happens on equal fingerprints, which are rare with a good prime. So the expected time is O(n + m). If almost every window collides, it can fall back to O(n * m). Extra room: a few numbers, O(1).

Watch out for

• Subtracting can make the number negative. Add Q before taking the remainder, as in the code.
• Keep every middle result small. Take % Q after each multiply so nothing overflows an int. For a large prime like 1_000_000_007, use long.
• A small prime like 101 makes collisions common. Real code uses a big prime, or two different hashes at once.
• If someone can pick the text to cause collisions, choose the base at random when the program starts.

What interviewers ask next

• Why use it instead of KMP? The rolling fingerprint works for many patterns of the same length at once (put their fingerprints in a set), and it extends to 2D grids and to "longest repeated substring" with binary search.
• Longest repeated substring? Binary search the length L. For each L, roll fingerprints of all windows and look for a repeat in a hash set. About O(n log n).
• How to make collisions very unlikely? Use two independent hashes with different bases and primes, and call it a match only when both agree.
• Count different substrings of length k? Roll the fingerprint and put each one in a set. Check letters on collisions if exact counts are needed.
• What is h for? It is how much the first letter is worth in the window, so you can take it out in one step.

Remember this

Grown-up words: the fingerprint is a hash, updating it while sliding is a rolling hash (a polynomial hash mod a prime), equal hashes for different words are a collision (a spurious hit), and the method is the Rabin Karp algorithm.