Offensive Security Researcher & Quantum Cryptography Analyst

Rabin-Karp Algorithm: A Detailed Explanation with Implementation

Abdul Wahab Junaid
The Rabin-Karp Algorithm: A Detailed Explanation

I use the Rabin-Karp algorithm whenever I need to search for a pattern within a text using hashing to quickly rule out positions that cannot possibly match, before falling back on direct character comparison only when a hash suggests a genuine match. I find this algorithm particularly elegant because it reframes string matching as a numeric comparison problem, and I especially value it when I need to search for multiple patterns simultaneously, since the hashing approach extends naturally to that case.

History and Background

I trace the Rabin-Karp algorithm to a 1987 paper by Richard M. Karp and Michael O. Rabin, titled “Efficient Randomized Pattern-Matching Algorithms,” published in the IBM Journal of Research and Development. I note that this algorithm emerged during a period of growing interest in randomized algorithms across computer science, and I regard it as one of the earliest and most influential applications of hashing to string processing. I see its ideas extend directly into later works, including plagiarism detection systems and the broader field of fingerprinting-based document comparison, cementing its practical relevance well beyond the original paper.

Problem Statement

I use Rabin-Karp to solve the standard pattern-matching problem: given a text $T$ of length $n$ and a pattern $P$ of length $m$, I want to find all occurrences of $P$ in $T$. Unlike KMP or the automaton method, which avoid redundant comparisons through clever pointer/state management, I want an approach that instead avoids redundant comparisons by using a cheaply updatable numeric fingerprint (a rolling hash) of each substring, comparing hashes first and only verifying character-by-character when hashes match.

Core Concepts

I rely on the concept of a rolling hash function, which allows me to compute the hash of the next substring in $O(1)$ time given the hash of the current substring, rather than recomputing the hash from scratch. I typically treat each substring as a number in some base $d$ (often related to the alphabet size), and I reduce this number modulo a prime $q$ to keep the values small and avoid overflow. I also rely on the distinction between a hash collision — where two different substrings produce the same hash value — and a true match, which is why I always perform a direct character verification whenever hashes match, since Rabin-Karp is a heuristic-filtering algorithm rather than one where hash equality alone certifies a match.

How It Works

I follow this process when performing Rabin-Karp matching:

  1. I choose a base $d$ (often the size of the character set) and a prime modulus $q$ to control hash value size and reduce collision probability.
  2. I compute the hash of the pattern $P$ and the hash of the first substring of $T$ of length $m$.
  3. I compare the pattern’s hash to the current substring’s hash. If they match, I perform a direct character-by-character comparison to rule out a false positive (hash collision).
  4. I “roll” the hash forward: I remove the contribution of the outgoing leftmost character and add the contribution of the new incoming rightmost character, in $O(1)$ time.
  5. I repeat steps 3–4 for every position in the text until I’ve checked all $n – m + 1$ possible starting positions.

Working Principle

I understand the internal logic of Rabin-Karp as trading exact per-character comparison for approximate but extremely cheap numeric comparison, verified only when necessary. The rolling hash mechanism is the key enabler: since I represent a substring as a polynomial evaluated at base $d$, shifting the window by one character corresponds to a simple linear transformation of the hash value — multiply by $d$, subtract the outgoing character’s contribution (scaled appropriately), and add the incoming character. This lets me maintain an always-current fingerprint of the current window in constant time per step, which is what allows the algorithm to scan the whole text in linear time on average, deferring the more expensive $O(m)$ character comparison to only the rare cases where hash values coincide.

Mathematical Foundation

I represent the pattern $P = p_0 p_1 \cdots p_{m-1}$ as a number in base $d$:

$$ h(P) = \left( \sum_{i=0}^{m-1} p_i \cdot d^{m-1-i} \right) \bmod q $$

I compute the hash of the text window starting at position $s$, $T[s..s+m-1]$, the same way, and I maintain it incrementally. Given the hash of the window starting at $s$, I compute the hash of the window starting at $s+1$ using:

$$ h(T[s+1..s+m]) = \left( d \cdot \big(h(T[s..s+m-1]) – T[s] \cdot d^{m-1}\big) + T[s+m] \right) \bmod q $$

I precompute $d^{m-1} \bmod q$ once, so this update takes $O(1)$ time per shift.

I analyze the probability of a hash collision (a “spurious hit”) using the properties of modular arithmetic: for a randomly and appropriately chosen prime $q$, the number of false collisions across all $n-m+1$ positions is bounded, in expectation, by:

$$ E[\text{false hits}] \le \frac{n}{q} \cdot O(m) $$

which I keep small by choosing $q$ sufficiently large (typically larger than $n \cdot m$) or by choosing $q$ randomly from a suitably large range of primes, following the Rabin-Karp fingerprinting analysis, ensuring the expected number of collisions remains a small constant.

I state the resulting expected time complexity of the algorithm:

$$ E[T(n)] = O(n + m) $$

while explicitly noting the worst-case time complexity, arising when many spurious hash collisions occur:

$$ T_{\text{worst}}(n) = O(nm) $$

Diagrams

flowchart TD
    A[Input: text T, pattern P, base d, prime q] --> B[Compute hash of P and first window of T]
    B --> C{Hash of window equals hash of P?}
    C -->|Yes| D[Verify with direct character comparison]
    D --> E{Characters actually match?}
    E -->|Yes| F[Record true match]
    E -->|No| G[Spurious hit, discard]
    C -->|No| H[Skip verification]
    F --> I{More text remaining?}
    G --> I
    H --> I
    I -->|Yes| J[Roll hash forward to next window]
    J --> C
    I -->|No| K[Return all matches]

Pseudocode

I write the pseudocode for the Rabin-Karp algorithm:

function RABIN_KARP(T, P, d, q):
    n = length(T)
    m = length(P)
    h = d^(m-1) mod q          // precomputed for rolling hash updates
    pHash = 0
    tHash = 0
    matches = empty list

    // I compute the initial hash values for P and the first window of T
    for i from 0 to m - 1:
        pHash = (d * pHash + P[i]) mod q
        tHash = (d * tHash + T[i]) mod q

    for s from 0 to n - m:
        if pHash == tHash:
            if T[s..s+m-1] == P:          // direct verification
                matches.append(s)

        if s

Step-by-Step Example

I search for pattern $P = \text{“26”}$ in text $T = \text{“3141592653589793”}$, using $d = 10$ (decimal digits) and $q = 101$ (a small prime for illustration).

I compute $h(P) = (2 \cdot 10 + 6) \bmod 101 = 26$.

I compute the hash of the first window “31”: $(3 \cdot 10 + 1) \bmod 101 = 31$. Not equal to 26, so I skip verification.

I roll forward to “14”: using the rolling formula, I compute $(10 \cdot (31 – 3\cdot10) + 4) \bmod 101 = (10 \cdot 1 + 4) \bmod 101 = 14$. Not equal to 26.

I continue rolling through “41”, “15”, “59”, “92”, “26” — and upon reaching the window “26” (starting at index 6 in “3141592653589793”), I compute its hash as 26, matching $h(P)$. I then verify directly: “26” equals “26”, confirming a true match at index 6.

I continue scanning the rest of the text similarly, checking each subsequent window, and I find no further occurrences of “26” in this particular text.

Time Complexity

I establish the expected-case time complexity of Rabin-Karp as $O(n + m)$, since the rolling hash update takes $O(1)$ per position and direct verification is triggered only rarely (in expectation, a small constant number of times) due to the low collision probability with a well-chosen modulus. I note the worst-case time complexity remains $O(nm)$, occurring when many or all hash comparisons happen to collide (either due to adversarial input or a poorly chosen modulus), forcing an $O(m)$ verification at nearly every position. I emphasize that, unlike KMP or the automaton method, Rabin-Karp’s strong performance guarantee is probabilistic/average-case rather than a guaranteed worst-case linear bound, which I consider its central theoretical trade-off.

Space Complexity

I require only $O(1)$ additional space beyond the input text and pattern, since I maintain just a few numeric variables (the current hash values, the precomputed power $d^{m-1} \bmod q$) regardless of $n$ or $m$. This compares favorably to the automaton method’s $O(m|\Sigma|)$ requirement, and is comparable to KMP’s $O(m)$ failure-function space, though I note Rabin-Karp needs even less since no auxiliary table is required at all.

Correctness Analysis

I justify the correctness of Rabin-Karp in two parts: soundness, since I never report a match unless the direct character-by-character verification succeeds, guaranteeing no false positives are ever returned regardless of hash collisions; and completeness, since I check every single position from $0$ to $n-m$ without skipping any, guaranteeing that if the hash comparison at a true-match position ever fails to trigger (which cannot happen, since identical substrings always produce identical hashes under a fixed hash function), no match would be missed — but because identical strings always hash identically, every true match’s hash will match the pattern’s hash, ensuring verification is always triggered at true-match positions. I therefore conclude the algorithm always finds every true occurrence and never reports a false one, with only its running time (not its correctness) affected by collision frequency.

Advantages

Disadvantages

Applications

I apply Rabin-Karp in:

Implementation in C

I implement the Rabin-Karp algorithm in C, with comments:

#include stdio.h>
#include string.h>

#define D 256   // number of characters in the input alphabet
#define Q 101   // a prime number used for the modulus

// I implement Rabin-Karp search for pattern P within text T
void rabinKarpSearch(char* T, char* P) {
    int n = strlen(T);
    int m = strlen(P);
    int h = 1;
    int pHash = 0, tHash = 0;

    // I precompute d^(m-1) mod q, used to remove the leading digit when rolling
    for (int i = 0; i  m - 1; i++) {
        h = (h * D) % Q;
    }

    // I compute the initial hash values for the pattern and the first window
    for (int i = 0; i  m; i++) {
        pHash = (D * pHash + P[i]) % Q;
        tHash = (D * tHash + T[i]) % Q;
    }

    for (int s = 0; s  n - m; s++) {
        if (pHash == tHash) {
            // I verify directly to rule out a spurious hash collision
            if (strncmp(T + s, P, m) == 0) {
                printf("Match found at index %d\n", s);
            }
        }

        if (s  n - m) {
            // I roll the hash forward by removing T[s] and adding T[s+m]
            tHash = (D * (tHash - T[s] * h) + T[s + m]) % Q;
            if (tHash  0) {
                tHash += Q; // I correct for a negative result from the modulo operation
            }
        }
    }
}

int main() {
    char T[] = "3141592653589793";
    char P[] = "26";

    rabinKarpSearch(T, P);

    return 0;
}

Sample Input and Output

I use T = "3141592653589793" and P = "26" as input, and I expect:

Match found at index 6

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version