Rabin-Karp Pattern Matching Algorithm

Problem

The Rabin-Karp algorithm finds a pattern in a text using rolling hashes, comparing hash values before falling back to a direct character check.

Input:  text = "abcabcabc", pattern = "cab"
Output: [2, 5]

Python Solution

def rabin_karp(text, pattern):
    n, m = len(text), len(pattern)
    if m > n:
        return []
    base, mod = 256, 10**9 + 7
    pattern_hash = 0
    window_hash = 0
    high_order = pow(base, m - 1, mod)
    result = []
    for i in range(m):
        pattern_hash = (pattern_hash * base + ord(pattern[i])) % mod
        window_hash = (window_hash * base + ord(text[i])) % mod
    for i in range(n - m + 1):
        if pattern_hash == window_hash and text[i:i + m] == pattern:
            result.append(i)
        if i < n - m:
            window_hash = ((window_hash - ord(text[i]) * high_order) * base + ord(text[i + m])) % mod
    return result

C++ Solution

vector<int> rabinKarp(string text, string pattern) {
    int n = text.size(), m = pattern.size();
    if (m > n) return {};
    const long base = 256, mod = 1000000007;
    long patternHash = 0, windowHash = 0, highOrder = 1;
    for (int i = 0; i < m - 1; i++) highOrder = (highOrder * base) % mod;
    for (int i = 0; i < m; i++) {
        patternHash = (patternHash * base + pattern[i]) % mod;
        windowHash = (windowHash * base + text[i]) % mod;
    }
    vector<int> result;
    for (int i = 0; i <= n - m; i++) {
        if (patternHash == windowHash && text.substr(i, m) == pattern) result.push_back(i);
        if (i < n - m) {
            windowHash = ((windowHash - text[i] * highOrder % mod + mod) * base + text[i + m]) % mod;
        }
    }
    return result;
}

Java Solution

class Solution {
    public List<Integer> rabinKarp(String text, String pattern) {
        int n = text.length(), m = pattern.length();
        List<Integer> result = new ArrayList<>();
        if (m > n) return result;
        long base = 256, mod = 1000000007, patternHash = 0, windowHash = 0, highOrder = 1;
        for (int i = 0; i < m - 1; i++) highOrder = (highOrder * base) % mod;
        for (int i = 0; i < m; i++) {
            patternHash = (patternHash * base + pattern.charAt(i)) % mod;
            windowHash = (windowHash * base + text.charAt(i)) % mod;
        }
        for (int i = 0; i <= n - m; i++) {
            if (patternHash == windowHash && text.substring(i, i + m).equals(pattern)) {
                result.add(i);
            }
            if (i < n - m) {
                windowHash = ((windowHash - text.charAt(i) * highOrder % mod + mod) * base + text.charAt(i + m)) % mod;
            }
        }
        return result;
    }
}

Complexity

Time: O(n + m) on average, since the rolling hash is updated in O(1) per shift and full character comparison only happens on a hash match; O(n · m) worst case if many hash collisions force full comparisons. Space: O(1) — only a few hash values are tracked.