The Rabin-Karp Algorithm

The Rabin-Karp algorithm is a string-searching algorithm developed by computer scientists Richard M. Karp and Michael O. Rabin in 1987. It identifies the presence of a pattern string within a larger text string by utilizing a mathematical hash function. Unlike other string-matching algorithms that rely on character-by-character comparisons and complex precomputed tables to skip sections of the text, the Rabin-Karp approach transforms the string-matching problem into a numerical comparison problem. It calculates a numerical hash value for the pattern and compares it against the hash values of all possible substrings of the same length within the text.^[25]

To achieve computational efficiency, the algorithm employs a rolling hash technique.^[26] This mathematical mechanism allows the hash value of a new substring to be computed in constant time by reusing the hash value of the immediately preceding substring. When the hash of a text window matches the hash of the pattern, the algorithm performs a direct character comparison to confirm the match, thereby ruling out false positives caused by hash collisions. This design results in an average-case time complexity that is linear relative to the combined lengths of the text and the pattern.

While the algorithm is highly effective for single-pattern matching, its primary advantage emerges in more complex applications. The rolling hash mechanism generalizes naturally to multiple-pattern matching, where a single pass over the text can search for thousands of patterns simultaneously. It also extends to two-dimensional pattern matching.^[27] Consequently, the underlying principles of the Rabin-Karp algorithm form the theoretical foundation for modern data deduplication systems, network file synchronization protocols, and automated plagiarism detection software.

Definition and Problem Statement

The fundamental problem in exact string matching is defined as follows: given a text string $T$ of length $n$ and a pattern string $P$ of length $m$ (where $m \le n$), the goal is to find all valid shifts $s$ such that the substring of $T$ starting at index $s$ exactly matches $P$. In mathematical terms, a valid shift $s$ (for $0 \le s \le n - m$) satisfies the condition $T[s \dots s+m-1] = P[0 \dots m-1]$. Both strings are composed of characters drawn from a finite alphabet $\Sigma$.

A naive or brute-force approach to this problem involves checking every possible shift $s$. For each shift, the algorithm compares the characters of $P$ against the characters of the text window $T[s \dots s+m-1]$ from left to right. If a mismatch occurs, the algorithm increments $s$ by one and begins the comparison again from the first character of the pattern. In the worst-case scenario, this approach is highly inefficient. For example, if the text consists of $n$ instances of the letter "A" and the pattern consists of $m-1$ instances of the letter "A" followed by a "B", the naive algorithm will successfully match the first $m-1$ characters at every shift before failing on the final character. This results in $m$ comparisons for each of the $n - m + 1$ windows, yielding a worst-case time complexity of $O(n \times m)$.

The Rabin-Karp algorithm addresses this inefficiency by applying a hash function to the strings.^[28] A hash function maps a sequence of characters to a single numerical value. The algorithm first computes the hash value of the pattern $P$. It then iterates through the text $T$, computing the hash value for each window of length $m$. If the hash value of the current text window differs from the hash value of the pattern, the two strings cannot possibly be identical, and the algorithm immediately moves to the next shift without performing any character comparisons.

If the hash values match, the algorithm performs a character-by-character verification to ensure the strings are truly identical. This verification step is necessary because different strings can occasionally produce the same hash value, a phenomenon known as a hash collision. If the hash function required $O(m)$ time to compute for every window, the total time complexity would remain $O(n \times m)$, offering no theoretical improvement over the naive approach. The defining feature of the Rabin-Karp algorithm is its use of a rolling hash, which allows the hash of the next window to be calculated from the hash of the current window in $O(1)$ time.^[26]

Mechanism and Operation

The efficiency of the Rabin-Karp algorithm relies entirely on the properties of its rolling hash function. The most common implementation uses a polynomial rolling hash, which treats the characters of a string as digits in a base-$b$ number system.

Let $b$ be a constant base, typically chosen to be the size of the character alphabet (for example, 256 for extended ASCII characters). Let $q$ be a large prime number. The hash value of a string $S$ of length $m$ is defined by the polynomial:

$H(S) = (S[0] \times b^{m-1} + S[1] \times b^{m-2} + \dots + S[m-1] \times b^0) \pmod q$

The modulo operation is strictly required to prevent integer overflow. Without it, the value $b^{m-1}$ would grow exponentially. For a pattern of length 100 and a base of 256, the hash value would require hundreds of digits to store, and arithmetic operations on such large numbers would take $O(m)$ time, defeating the purpose of the rolling hash. By applying modulo $q$, all values fit within standard CPU registers, ensuring that arithmetic operations execute in $O(1)$ time. The prime $q$ is usually chosen to be as large as possible such that $b \times q$ fits within the maximum integer size of the architecture (such as a 32-bit or 64-bit integer).

To compute the hash of the first window of the text $T[0 \dots m-1]$, the algorithm evaluates this polynomial in $O(m)$ time. When the window slides one position to the right, the new window is $T[1 \dots m]$. The hash of this new window can be derived directly from the hash of the old window using a constant number of arithmetic operations.

The mathematical update rule is:
$H(T[1 \dots m]) = ( (H(T[0 \dots m-1]) - T[0] \times b^{m-1}) \times b + T[m] ) \pmod q$

In this formula, the algorithm subtracts the value of the character leaving the window ($T[0]$ multiplied by $b^{m-1}$), multiplies the entire remaining result by the base $b$ to shift all characters one position to the left, and adds the value of the new character entering the window ($T[m]$). Because the value $b^{m-1} \pmod q$ is constant for a given pattern length $m$, it is precomputed once at the start of the algorithm. Consequently, updating the hash takes $O(1)$ time.

To illustrate this mechanism, consider a base $b = 10$ and a prime $q = 13$. Suppose the text is the string "31415" and the pattern is "14". The length of the pattern $m$ is 2. The precomputed multiplier is $10^{2-1} \pmod{13} = 10$.
First, the algorithm computes the hash of the pattern "14":
$H("14") = (1 \times 10 + 4) \pmod{13} = 14 \pmod{13} = 1$.
Next, it computes the hash of the first text window "31":
$H("31") = (3 \times 10 + 1) \pmod{13} = 31 \pmod{13} = 5$.
Since 5 does not equal 1, the algorithm slides the window to "14". Instead of computing the hash from scratch, it uses the update rule:
$H("14") = ((5 - 3 \times 10) \times 10 + 4) \pmod{13}$.
Here, $5 - 30 = -25$. In modulo 13 arithmetic, $-25 \equiv 1$. Then $(1 \times 10) + 4 = 14$, and $14 \pmod{13} = 1$.
The hash of the new window matches the hash of the pattern. The algorithm then performs a direct character comparison between the text window "14" and the pattern "14", confirming the match.

function RabinKarp(text, pattern, b, q):
    n = length(text)
    m = length(pattern)
    h_pattern = 0
    h_text = 0
    h_multiplier = 1

    # Precompute b^(m-1) modulo q
    for i from 1 to m - 1:
        h_multiplier = (h_multiplier * b) mod q

    # Calculate initial hash values for pattern and first text window
    for i from 0 to m - 1:
        h_pattern = (b * h_pattern + pattern[i]) mod q
        h_text = (b * h_text + text[i]) mod q

    # Slide the pattern over text one by one
    for s from 0 to n - m:
        if h_pattern == h_text:
            # Hash match found, verify characters
            if text[s ... s+m-1] == pattern[0 ... m-1]:
                return s
        
        # Calculate hash for next window
        if s < n - m:
            h_text = (b * (h_text - text[s] * h_multiplier) + text[s + m]) mod q
            if h_text < 0:
                h_text = h_text + q

    return -1

The time complexity of the Rabin-Karp algorithm is $O(n + m)$ in the best and average cases. The preprocessing step to compute the initial hashes and the multiplier takes $O(m)$ time. The main loop runs $n - m + 1$ times, taking $O(1)$ time per iteration for the hash update. If the hash function distributes values uniformly, collisions are rare, and the $O(m)$ character verification is executed infrequently. In their original probabilistic analysis, Karp and Rabin demonstrated that if $q$ is a randomly chosen prime from a sufficiently large range (for example, $[2, n^2 \times m]$), the probability of a false positive is bounded by $O(1/n)$, ensuring the expected number of false matches is extremely small.

However, the worst-case time complexity is $O(n \times m)$. This occurs if the hash function produces a collision at every shift, forcing the algorithm to perform a full character-by-character comparison each time. The space complexity is $O(1)$ auxiliary space, as the algorithm only needs to store a few integer variables regardless of the text or pattern size.

Discovery and Historical Context

The Rabin-Karp algorithm was formalized by computer scientists Richard M. Karp and Michael O. Rabin. They published their findings in 1987 in the IBM Journal of Research and Development under the title "Efficient randomized pattern-matching algorithms" Efficient randomized pattern-matching algorithms^[1].

Prior to their publication, the exact string-matching problem had already been solved in linear time by other researchers.^[29] In 1977, Donald Knuth, James H. Morris, and Vaughan Pratt published the Knuth-Morris-Pratt algorithm, which utilizes an automaton and a precomputed failure function to skip unnecessary comparisons Fast Pattern Matching in Strings^[2]. In the same year, Robert S. Boyer and J. Strother Moore introduced the Boyer-Moore algorithm, which scans patterns from right to left and uses bad-character and good-suffix heuristics to achieve sub-linear performance in practice A Fast String Searching Algorithm^[3]. Additionally, Alfred Aho and Margaret Corasick had developed the Aho-Corasick algorithm in 1975, which solved the multiple-pattern matching problem in linear time by constructing a finite state machine Efficient string matching: an aid to bibliographic search^[4].^[30]

Despite the existence of these highly efficient algorithms, Karp and Rabin sought a different approach. They aimed to create a randomized algorithm that was conceptually simpler, required only constant auxiliary storage, and could be easily generalized to higher-dimensional arrays. Their work built upon a mathematical framework established by Rabin six years earlier. In 1981, Rabin authored a technical report at Harvard University titled "Fingerprinting by Random Polynomials" Fingerprinting by Random Polynomials^[5]. This report introduced the concept of representing large data objects with short, fixed-length numerical fingerprints using polynomial arithmetic over finite fields, specifically Galois field GF(2) Rabin fingerprint^[6].

By applying this fingerprinting technique to the sliding window of a text string, Karp and Rabin created the rolling hash mechanism. Their 1987 paper demonstrated that string matching could be treated as a numerical problem rather than a purely combinatorial one. The algorithm is classified as a Las Vegas randomized algorithm because it always returns the correct answer, but its running time depends on the probabilistic avoidance of hash collisions Introduction to Algorithms^[7].^[27]

Important Variants

The core concept of the rolling hash has been adapted into several important variants to solve problems beyond single-pattern string matching.

Multiple Pattern Matching

The most prominent variant of the Rabin-Karp algorithm is its application to multiple pattern matching. When searching for $k$ different patterns of the same length $m$ within a text, the algorithm computes the hash value for all $k$ patterns and stores them in a hash table or a Bloom filter Space/time trade-offs in hash coding with allowable errors^[8]. As the rolling hash of the text is computed, the algorithm checks if the current text hash exists in the set of pattern hashes. This reduces the time complexity from $O(k \times n)$ (which would be required by running a single-pattern search $k$ times) to $O(n + k \times m)$ average time. This variant is highly memory-efficient compared to the Aho-Corasick automaton, which requires building a large state machine that can consume significant memory for large pattern sets Algorithms on Strings, Trees, and Sequences^[9].

Two-Dimensional Pattern Matching

The algorithm generalizes naturally to two-dimensional pattern matching, where the goal is to find an $m \times m$ matrix pattern within an $n \times n$ text matrix. Instead of a linear window, a rectangular window rolls across the text matrix. To achieve this efficiently, the algorithm first computes a one-dimensional hash for each column of the pattern, resulting in a one-dimensional array of $m$ hashes. It then computes a hash of this array. For the text, it computes the column hashes for all columns of height $m$, and then rolls a horizontal window of width $m$ across these column hashes. This reduces a two-dimensional problem into a one-dimensional problem, maintaining linear time complexity relative to the size of the text matrix. This multidimensional capability was one of the primary motivations cited by Karp and Rabin in their original paper String-searching algorithm^[10].

Alternative Rolling Hashes

While the original algorithm uses modular arithmetic, modern implementations often substitute the polynomial hash with bitwise rolling hashes to improve execution speed on modern processors. In 1997, Jonathan D. Cohen introduced Buzhash, a cyclic polynomial hash that replaces slow modulo operations and integer multiplication with fast bitwise XOR and barrel shift operations Recursive hashing functions for n-grams^[11]. These bitwise variants maintain the $O(1)$ update time while significantly reducing the constant factor of the algorithm's running time Rolling hash^[12].

Real-World Applications

While algorithms like Boyer-Moore are generally preferred for simple text editor searches, the Rabin-Karp algorithm and its underlying rolling hash primitive are heavily utilized in systems that require the detection of similarity, redundancy, or exact matches across massive datasets.

Plagiarism Detection

The algorithm is a foundational component of automated plagiarism detection systems. In 1994, Alex Aiken at UC Berkeley developed MOSS (Measure of Software Similarity), a system designed to detect plagiarism in programming assignments Moss - A Measure Of Software Similarity^[13]. MOSS tokenizes source code to ignore whitespace and variable names, then uses a rolling hash to generate fingerprints of the code.

To handle large documents efficiently, MOSS divides the document into overlapping substrings of length $k$ (k-grams) and computes the rolling hash for each. In 2003, Saul Schleimer, Daniel S. Wilkerson, and Alex Aiken formalized a technique called "winnowing," which groups these hashes into windows of size $w$ and selects the minimum hash value in each window to represent the document Winnowing: local algorithms for document fingerprinting^[14]. This guarantees that any matching substring of length $w+k-1$ will be detected, while significantly reducing the database size. This allows the system to identify copied code even if the student has reordered functions or inserted irrelevant statements. Similar techniques are used by other plagiarism detectors like JPlag JPlag: Detecting Software Plagiarism^[15].

Data Deduplication and Network File Systems

Rabin-Karp fingerprinting is heavily used in storage systems to eliminate redundant data. In 2001, Athicha Muthitacharoen, Benjie Chen, and David Mazières introduced the Low-Bandwidth Network File System (LBFS) A low-bandwidth network file system^[16]. LBFS uses a rolling hash to perform content-defined chunking.

Traditional file systems divide files into fixed blocks (for example, 4 kilobytes). This creates a boundary shift problem: if a user inserts a single byte at the beginning of a file, every subsequent byte shifts by one position, causing every fixed block to change its hash and defeating deduplication. LBFS solves this by computing a rolling hash over the file and declaring a block boundary whenever the lower bits of the hash match a specific predetermined value. Because the boundaries are defined by the local content rather than absolute file offsets, an insertion or deletion of a single byte only alters the chunk containing that byte. The rest of the file's chunks remain identical, allowing the system to deduplicate the unchanged chunks. This content-defined chunking method is now standard in enterprise deduplication systems, such as those developed by Data Domain Avoiding the disk bottleneck in the Data Domain deduplication file system^[17] and in academic research for finding similar files Finding similar files in a large file system^[18].

File Synchronization

The Rsync utility, created by Andrew Tridgell and Paul Mackerras in 1996, uses a rolling checksum to synchronize files across a network efficiently The rsync algorithm. While Rsync originally utilized a rolling hash based on Adler-32 rather than Rabin's polynomial, the conceptual framework is identical to the Rabin-Karp algorithm. The system computes the rolling hash of a local file and compares it against the hashes of blocks from a remote file, transmitting only the blocks that do not match.

Language and Library Implementations

The polynomial hash function defined by Karp and Rabin is frequently used as the default string hashing mechanism in programming languages. For instance, the hashCode() method for the String class in the Java programming language uses a polynomial hash with a base of 31, directly mirroring the mathematical structure of the Rabin-Karp hash Java Platform, Standard Edition 17 API Specification: java.lang.String^[19]. This is distinct from cryptographic hash functions like SHA-256, which are designed for security rather than rolling updates FIPS 180-4: Secure Hash Standard (SHS)^[20] and hashlib, Secure hashes and message digests^[21].

Significance and Tradeoffs

The Rabin-Karp algorithm occupies a specific niche in computer science Algorithms^[22]. Its primary significance lies in the conceptual shift it introduced: reducing the combinatorial problem of string matching to a numerical problem of polynomial evaluation.^[25] The rolling hash primitive has proven to be highly adaptable, scaling from simple string searches to complex, multi-gigabyte file deduplication systems Rabin, Karp algorithm^[23].

However, the algorithm presents specific tradeoffs. For single-pattern matching, it is generally outperformed in practice by the Boyer-Moore algorithm, which can skip large sections of the text entirely.^[29] The Rabin-Karp algorithm requires integer multiplication and modulo arithmetic for every character in the text. These mathematical operations are computationally more expensive than the simple character equality checks and array lookups used by the Knuth-Morris-Pratt algorithm.

The worst-case time complexity of $O(n \times m)$ is another limitation. If an adversary knows the prime number $q$ and the base $b$ used by the hash function, they can construct a text and a pattern that intentionally generate hash collisions at every position. This forces the algorithm to perform a full $O(m)$ character verification at every shift, degrading its performance to that of the naive search. This vulnerability is a form of algorithmic complexity attack, where malicious inputs are designed to trigger the worst-case execution time of an algorithm Denial of Service via Algorithmic Complexity Attacks^[24]. To mitigate this in security-sensitive applications, implementations often select the prime $q$ and the base $b$ randomly at runtime, making it mathematically improbable for an adversary to force continuous collisions.

Despite these tradeoffs, the algorithm remains highly relevant. When searching for multiple patterns, or when the problem requires identifying similarities rather than exact matches, the Rabin-Karp algorithm and its rolling hash provide a highly efficient, low-memory solution that deterministic automata cannot easily replicate.