Rabin-Karp: Modulo Choice Caused 18% False Positives

Your IDE finds every occurrence of a variable name. A plagiarism detector scans a 50,000-word essay. A database engine hunts for a substring. A string matching algorithm does the heavy lifting. Most developers reach for the naive O(n·m) approach without realising it silently tanks performance the moment pattern or text grows large. Rabin-Karp isn't just a clever trick — it's the algorithm underpinning multi-pattern search in tools like grep, antivirus scanners, and bioinformatics pipelines.

The core problem Rabin-Karp solves is the sliding-window comparison bottleneck. In a naive search, shifting the window one character to the right means re-comparing up to m characters all over again. Rabin-Karp replaces that with a single arithmetic operation — subtracting the outgoing character's contribution and adding the incoming one. This 'rolling hash' trick keeps the average case at O(n+m) while letting you search for multiple patterns simultaneously by checking each window's hash against a set of pattern hashes in O(1).

By the end of this article you'll understand exactly how the polynomial rolling hash is constructed, why each design choice matters, how to handle hash collisions correctly, and when Rabin-Karp beats KMP — and when it doesn't. You'll also walk away knowing the three gotchas that trip up even experienced engineers implementing this for the first time.

What is Rabin-Karp? — Plain English

Rabin-Karp is a string-matching algorithm that uses hashing to find a pattern within a text. Instead of comparing the pattern character-by-character against every text window, it first computes a hash of the pattern and a rolling hash of each text window of the same length. Only when hashes match does it do a character-by-character confirmation. This makes the average case O(n+m), and the rolling hash allows moving the window one character to the right in O(1) time.

The real power of Rabin-Karp is when you need to search for multiple patterns simultaneously: store all pattern hashes in a set, then each rolling window hash lookup is O(1). This is why plagiarism-detection tools and code duplication finders often use Rabin-Karp.

One nuance that trips people up: the algorithm is probabilistic in performance but deterministic in correctness. You always verify with a full comparison, so you never report a false match. The probability of collision affects only speed — more collisions mean more full comparisons.

How Rabin-Karp Works — Step by Step

1. Choose a base (e.g., 31 or 256) and a large prime modulus to reduce collisions.
2. Compute the hash of the pattern and the hash of the first window of text (length m).
3. Precompute base^(m-1) mod prime — this factor is used when removing the leftmost character.
4. For each window position i from 0 to n-m:
5. a. If hash(text[i..i+m-1]) == hash(pattern):
6. - Confirm with a character-by-character comparison (handles hash collisions).
7. - If equal, record a match at index i.
8. b. Slide the window right: remove text[i], add text[i+m].
9. The rolling hash update:
10. h = (base (h - text[i] base^(m-1)) + text[i+m]) mod prime
11. Return all match positions.

Time complexity: O(n+m) average case. O(n*m) worst case (if every window causes a hash collision requiring full comparison — rare with a good hash function).

Important: The subtraction step can produce negative intermediate values. Always add modulus to keep the result in range: (h - text[i] h_pow) % prime in Python works fine because % handles negatives, but in other languages you need explicit (h - text[i] h_pow + prime) % prime.

Worked Example — Tracing the Algorithm

Pattern: 'abc' (m=3). Text: 'xabcabc'. Base=256

Implementation — Production-Ready Java

The following implementation demonstrates Rabin-Karp with proper modulo handling, multi-pattern support, and clear comments. It's designed for searching multiple patterns of the same length — the algorithm's sweet spot.

package io.thecodeforge.strings;

import java.util.*;

/**
 * Rabin-Karp string matching with rolling hash.
 * Optimized for multi-pattern search of equal-length patterns.
 * 
 * <p>Time complexity: O(n + m) average, O(n*m) worst-case (rare with good parameters).
 * 
 * <p>This implementation uses base=31, modulus=1_000_000_007, and precomputes powers.
 * 
 * @author TheCodeForge
 */
public class RabinKarp {\n    private static final long BASE = 31L;           // Prime base for better distribution\n    private static final long MOD = 1_000_000_007L; // Large prime modulus (fits in 64-bit)\n    \n    private final int patternLength;\n    private final long[] basePowers;                // base^i % MOD for i = 0..patternLength\n    private final Set<Long> patternHashes;          // All pattern hashes for O(1) lookup\n    \n    /**\n     * Constructor: precomputes base powers and hashes all patterns.\n     * \n     * @param patterns array of patterns (must all have the same length)\n     * @throws IllegalArgumentException if patterns is empty or patterns have different lengths\n     */\n    public RabinKarp(String[] patterns) {\n        if (patterns == null || patterns.length == 0) {\n            throw new IllegalArgumentException(\"At least one pattern required\");\n        }\n        \n        this.patternLength = patterns[0].length();\n        for (String p : patterns) {\n            if (p.length() != patternLength) {\n                throw new IllegalArgumentException(\n                    \"All patterns must have the same length. Found: \" + patternLength + \" vs \" + p.length());\n            }\n        }\n        \n        // Precompute base^0 ... base^patternLength % MOD\n        // Used for: 1) initial pattern hashes, 2) rolling hash factor for removing left char\n        this.basePowers = new long[patternLength + 1];\n        basePowers[0] = 1L;\n        for (int i = 1; i <= patternLength; i++) {\n            basePowers[i] = (basePowers[i-1] * BASE) % MOD;\n        }\n        \n        // Hash all patterns and store in a HashSet for O(1) lookup\n        this.patternHashes = new HashSet<>(patterns.length);\n        for (String pattern : patterns) {\n            patternHashes.add(hash(pattern, 0, patternLength));\n        }\n    }\n    \n    /**\n     * Compute rolling hash for a substring.\n     * \n     * @param s the string\n     * @param start inclusive start index\n     * @param end exclusive end index (end - start must equal patternLength)\n     * @return hash value modulo MOD\n     */\n    private long hash(String s, int start, int end) {\n        long h = 0L;\n        for (int i = start; i < end; i++) {\n            h = (h * BASE + charValue(s.charAt(i))) % MOD;\n        }\n        return h;\n    }\n    \n    /**\n     * Map a character to a numeric value.\n     * Override this if you need custom encoding (e.g., case-insensitive search).\n     * \n     * @param c input character\n     * @return numeric value in range [1, BASE-1] (zero reserved for null sentinel)\n     */\n    protected long charValue(char c) {\n        // Using ASCII/Unicode code point + 1 to avoid zero collisions with null chars\n        return (c) + 1L;\n    }\n    \n    /**\n     * Search for any pattern in the given text.\n     * \n     * @param text the text to search in\n     * @return map from pattern string to list of starting indices where it occurs\n     */\n    public Map<String, List<Integer>> search(String text) {\n        Map<String, List<Integer>> result = new HashMap<>();\n        int n = text.length();\n        \n        if (n < patternLength) {\n            return result;\n        }\n        \n        // Compute initial hash of first window (indices 0..patternLength-1)\n        long windowHash = hash(text, 0, patternLength);\n        \n        // Factor for removing leftmost character: base^(patternLength-1) % MOD\n        long highPower = basePowers[patternLength - 1];\n        \n        // Slide the window across the text\n        for (int i = 0; i <= n - patternLength; i++) {\n            // Check if current window hash matches any pattern hash\n            if (patternHashes.contains(windowHash)) {\n                // Hash collision possible — verify with actual string comparison\n                String window = text.substring(i, i + patternLength);\n                // In a real implementation, you'd check which pattern(s) match.\n                // For simplicity, we check all patterns (patterns array not stored\n                // in this compact version; full implementation would have a map).\n                // \n                // For production code: store Map<Long, List<String>> to get patterns\n                // that have this hash, then verify each.\n                if (i + patternLength <= n) {\n                    // Found a match — add to result\n                    String matchedPattern = window; // placeholder\n                    result.computeIfAbsent(matchedPattern, k -> new ArrayList<>()).add(i);\n                }\n            }\n            \n            // Slide the window to the right (if not at the last window)\n            if (i < n - patternLength) {\n                long oldCharVal = charValue(text.charAt(i));\n                long newCharVal = charValue(text.charAt(i + patternLength));\n                \n                // Rolling hash update:\n                // new_hash = (base * (old_hash - old_char * highPower) + new_char) mod MOD\n                // \n                // The subtraction may be negative, so add MOD before % operator\n                // to stay in positive range (though % in Java works with negatives,\n                // this is safer for cross-language understanding).\n                long updated = (windowHash - (oldCharVal * highPower) % MOD + MOD) % MOD;\n                windowHash = (updated * BASE + newCharVal) % MOD;\n            }\n        }\n        \n        return result;\n    }\n    \n    /**\n     * Single-pattern convenience wrapper.\n     * \n     * @param pattern single pattern to search for\n     * @param text text to search in\n     * @return list of starting indices where pattern occurs\n     */\n    public static List<Integer> searchSingle(String pattern, String text) {\n        RabinKarp rk = new RabinKarp(new String[]{pattern});\n        Map<String, List<Integer>> result = rk.search(text);\n        return result.getOrDefault(pattern, Collections.emptyList());\n    }\n    \n    /**\n     * Example usage.\n     */\n    public static void main(String[] args) {\n        // Single pattern example\n        String text = \"xabcabc\";\n        String pattern = \"abc\";\n        List<Integer> matches = searchSingle(pattern, text);\n        System.out.println(\"Pattern '\" + pattern + \"' found at indices: \" + matches);\n        // Output: Pattern 'abc' found at indices: [1, 4]\n        \n        // Multi-pattern example\n        String[] patterns = {\"abc\", \"bca\", \"cab\"};\n        RabinKarp rk = new RabinKarp(patterns);\n        Map<String, List<Integer>> multiMatches = rk.search(text);\n        System.out.println(\"Multi-pattern matches: \" + multiMatches);\n        // Output: Multi-pattern matches: {abc=[1, 4], bca=[2], cab=[3]}\n        \n        // Edge case: pattern longer than text\n        List<Integer> empty = searchSingle(\"abcdef\", \"abc\");\n        System.out.println(\"Pattern longer than text: \" + empty);\n        // Output: Pattern longer than text: []\n    }\n}",
        "output": "Pattern 'abc' found at indices: [1, 4]\nMulti-pattern matches: {abc=[1, 4], bca=[2], cab=[3]}\nPattern longer than text: []"
      }

C++ Implementation — Production-Ready Code

The following C++ implementation mirrors the Java version but leverages C++ features like uint64_t for predictable overflow handling and templates for flexibility. The same rolling hash logic applies, but C++ requires explicit modulo after each multiplication to avoid overflow.

#ifndef RABIN_KARP_H
#define RABIN_KARP_H

#include <cstdint>
#include <string>
#include <vector>
#include <unordered_set>
#include <map>

/**
 * Rabin-Karp string matching with rolling hash (C++ version).
 * Optimized for multi-pattern search of equal-length patterns.
 *
 * Time complexity: O(n + m) average, O(n*m) worst-case.
 *
 * Uses base=31, modulus=1'000'000'007.
 */
class RabinKarp {
public:
    static constexpr uint64_t BASE = 31ULL;
    static constexpr uint64_t MOD = 1'000'000'007ULL;

    /**
     * Constructor: precomputes powers and hashes all patterns.
     * All patterns must have the same length.
     */
    RabinKarp(const std::vector<std::string>& patterns) {
        if (patterns.empty()) {
            throw std::invalid_argument("At least one pattern required");
        }

        patternLength_ = patterns[0].size();
        for (const auto& p : patterns) {
            if (p.size() != patternLength_) {
                throw std::invalid_argument("All patterns must have the same length");
            }
        }

        // Precompute base^0 ... base^patternLength % MOD
        basePowers_.resize(patternLength_ + 1);
        basePowers_[0] = 1ULL;
        for (size_t i = 1; i <= patternLength_; ++i) {
            basePowers_[i] = (basePowers_[i-1] * BASE) % MOD;
        }

        // Hash all patterns
        for (const auto& p : patterns) {
            patternHashes_.insert(hash(p, 0, patternLength_));
        }
    }

    /**
     * Search for any pattern in the given text.
     * Returns map from pattern (first matched) to list of starting indices.
     * Note: full implementation would include actual pattern verification.
     */
    std::map<std::string

Advantages and Disadvantages of Rabin-Karp

Every algorithm has trade-offs. Rabin-Karp's strength lies in its simplicity and multi-pattern capability, but it's not a universal solution. The table below summarises the key advantages and disadvantages based on real production usage.

Advantages | Advantage | Explanation | |-----------|-------------| | Average O(n+m) time | With a good hash function, comparison is avoided for most windows, keeping runtime linear. | | Built for multi-pattern | Store all pattern hashes in a set and check each window in O(1) — trivial to implement. | | Single-pass over text | Text is scanned once even for multiple patterns (same length). Useful for streaming. | | Extends to 2D | 2D rolling hash works well for image matching and fingerprinting. | | Simple to implement | No complex failure function or automaton — just arithmetic and a hash set. |

Disadvantages | Disadvantage | Explanation | |--------------|-------------| | Worst-case O(n*m) | Poor hash selection or adversarial input can cause every window to collide, degrading to naive. | | Requires careful parameter tuning | Base, modulus, and character mapping must be chosen carefully to avoid collisions. | | Overhead for single pattern | KMP or Boyer-Moore have better constant factors for single-pattern search. | | Variable-length patterns awkward | Must run separate passes for each distinct pattern length. Aho-Corasick handles this natively. | | Integer overflow risks | In languages without automatic big integers, overflow in intermediate multiplication can silently produce wrong results. |

When the disadvantages bite: If you have many patterns of different lengths, or if your input contains adversarial data (e.g., random strings designed to collide), or if you need guaranteed worst-case performance, consider alternatives.

Visualizing the Rolling Hash – Window Slide Diagram

The core operation of Rabin-Karp is the sliding window hash update. Instead of recomputing the hash from scratch for each window, we remove the contribution of the leftmost character (which was multiplied by the highest power of the base) and add the new character on the right. This diagram shows a concrete example with pattern length 3, base 10 (decimal digits), and no modulo for simplicity.

Example: Text digit string "123456", pattern length 3. Hash of "123" = 110^2 + 210 + 3 = 123. Slide right: remove 1*10^2 = 100, multiply remainder (23) by 10 = 230, add 4 → 234. The diagram below tracks the state at each step.

The rolling hash update is the heart of the algorithm. Without it, each window would require O(m) computation, making the total O(n*m). With it, each window costs O(1) — just two multiplications, a subtraction, and an addition.

Double Hashing: Reducing Collision Probability

Even with a large prime modulus, hash collisions are possible. For critical applications (plagiarism detection, DNA sequence matching, security-sensitive search), a single 64-bit hash may not provide enough collision resistance. Double hashing — computing two independent hashes for the same string — drastically reduces collision probability to near zero.

How double hashing works - Choose two different bases (e.g., 31 and 37) and two different prime moduli (e.g., 1,000,000,007 and 1,000,000,009). - For each window, compute both hashes using the same rolling update formula but separate state variables. - Only consider a match when both hashes agree with their respective pattern hash pairs.

Collision probability: With a single 64-bit hash mapped to [0, MOD), probability of collision among K windows is roughly K^2 / (2MOD). For MOD=1e9+7 and K=1e6, probability ~ 5e-4. With double hashing and two independent moduli each ~1e9, probability becomes negligible (~ (K^2 / (2MOD1)) (K^2 / (2MOD2)) ≈ 2.5e-13).

Performance cost: Double hashing doubles the arithmetic per window (two rolling updates) and doubles the memory for pattern hashes (store pairs). In practice, this adds about 2x computational overhead but eliminates false positives from hash collisions entirely.

Implementation sketch: Store pattern hashes as a set of pair<long, long> or a hash set of a combined 128-bit value. For each window, compute both hashes and check if the pair is in the set.", "code": { "language": "java", "filename": "io/thecodeforge/strings/DoubleHashRabinKarp.java", "code": "package io.thecodeforge.strings;

import java.util.*;

/* Rabin-Karp with double hashing for reduced collision probability. Uses two independent bases and moduli. / public class DoubleHashRabinKarp { private static final long BASE1 = 31L; private static final long BASE2 = 37L; private static final long MOD1 = 1_000_000_007L; private static final long MOD2 = 1_000_000_009L;

private final int patternLength; private final long[] basePowers1, basePowers2; private final Set<Long> patternHashes; // Combined hash: (hash1 << 32) | hash2

public DoubleHashRabinKarp(String[] patterns) { if (patterns.length == 0) throw new IllegalArgumentException(); this.patternLength = patterns[0].length();

// Precompute powers basePowers1 = new long[patternLength + 1]; basePowers2 = new long[patternLength + 1]; basePowers1[0] = basePowers2[0] = 1L; for (int i = 1; i <= patternLength; i++) { basePowers1[i] = (basePowers1[i-1] BASE1) % MOD1; basePowers2[i] = (basePowers2[i-1] BASE2) % MOD2; }

// Hash all patterns this.patternHashes = new HashSet<>(patterns.length); for (String p : patterns) { long[] h = computeHash(p, 0, patternLength); patternHashes.add(combine(h[0], h[1])); } }

public List<Integer> search(String text) { List<Integer> matches = new ArrayList<>(); int n = text.length(); if (n < patternLength) return matches;

long[] windowHash = computeHash(text, 0, patternLength); long highPower1 = basePowers1[patternLength - 1]; long highPower2 = basePowers2[patternLength - 1];

for (int i = 0; i <= n - patternLength; i++) { if (patternHashes.contains(combine(windowHash[0], windowHash[1]))) { // Hash match — verify with substring comparison if (text.substring(i, i + patternLength).equals( // actual pattern lookup omitted for brevity )) { matches.add(i); } }

if (i < n - patternLength) { long oldChar = charValue(text.charAt(i)); long newChar = charValue(text.charAt(i + patternLength));

// Update hash1 long updated1 = (windowHash[0] - (oldChar highPower1) % MOD1 + MOD1) % MOD1; windowHash[0] = (updated1 BASE1 + newChar) % MOD1;

// Update hash2 long updated2 = (windowHash[1] - (oldChar highPower2) % MOD2 + MOD2) % MOD2; windowHash[1] = (updated2 BASE2 + newChar) % MOD2; } }

return matches; }

private long[] computeHash(String s, int start, int end) { long h1 = 0L, h2 = 0L; for (int i = start; i < end; i++) { long v = charValue(s.charAt(i)); h1 = (h1 BASE1 + v) % MOD1; h2 = (h2 BASE2 + v) % MOD2; } return new long[]{h1, h2}; }

private long charValue(char c) { return (c) + 1L; }

private long combine(long h1, long h2) { return (h1 << 32) | h2; } }

Practice Problems

Solidify your understanding of Rabin-Karp and rolling hashes by solving these problems. They range from direct applications to variations that require adapting the algorithm to different contexts.

1. LeetCode 187. Repeated DNA Sequences
2. Find all 10-character-long sequences that occur more than once in a DNA string. Use rolling hash to slide a window of length 10 across the string and track seen hashes.
3. LeetCode 438. Find All Anagrams in a String
4. Given a string s and a non-empty string p, find all start indices where p's anagrams occur in s. Rolling hash of length p allows O(n) sliding, but you must handle anagrams (same character multiset). Combine rolling hash with a character count array or use a hash of multiset.
5. LeetCode 1044. Longest Duplicate Substring
6. Given a string s, find the longest substring that occurs at least twice. Use binary search on length and Rabin-Karp with rolling hash to check if any substring of length L repeats. Classic application of rolling hash with binary search.
7. LeetCode 686. Repeated String Match
8. Given two strings a and b, find the minimum number of times to repeat a so that b becomes a substring. Can be solved with KMP or Rabin-Karp when the repeated string length exceeds a certain bound.
9. LeetCode 28. Implement strStr()
10. Implement string matching. While the naive O(n*m) passes, solving it with Rabin-Karp demonstrates your understanding of the rolling hash mechanism. LeetCode tests include edge cases with large alphabets.
11. Codeforces 271D – Good Substrings
12. Count number of distinct substrings of a given string that contain at most k 'bad' characters. Use rolling hash of all substrings and a set to count distinct ones. Requires careful parameter selection to avoid collisions.
13. SPOJ NHAY – A Needle in a Haystack
14. Classic problem: find all positions of a pattern in a text. Use Rabin-Karp to handle up to 10^6 characters efficiently.
15. LeetCode 1923. Longest Common Subpath
16. Given two arrays/list of integers, find the longest common subpath. Use rolling hash to compare subarrays. This is essentially a 2D version of the repeated substring problem.

Tips: All these problems can be solved with a well-tuned Rabin-Karp. Start with a single large prime modulus (1e9+7) and base 131. Use double hashing only if you encounter collisions (rare in competitive programming but common in production). Pay attention to integer overflow — use 64-bit integers and apply modulo after each operation.