How the Rabin-Karp Algorithm Uses Rolling Hash for String Matching

The Rabin-Karp algorithm accelerates substring search by comparing polynomial hashes of text windows rather than performing character-by-character comparisons, achieving O(N + M) complexity by updating hashes in constant time as the window slides.

The Rabin-Karp algorithm is a string-searching algorithm that leverages a rolling hash to locate patterns efficiently within large texts. In the trekhleb/javascript-algorithms repository, the implementation pairs a sliding window technique with polynomial hashing to minimize redundant computations. This article examines how the rolling hash mechanism processes text in linear time by analyzing the actual source code and demonstrating practical implementations.

Core Mechanics of Rolling Hash

The algorithm treats each substring as a number in a base representation (typically base 256 for ASCII or a large prime), computes its hash, and "rolls" the calculation forward as the search window moves. This avoids rehashing the entire window from scratch for every position.

Hashing the Pattern

Before scanning the text, the algorithm computes the hash of the search pattern once. In src/algorithms/cryptography/polynomial-hash/PolynomialHash.js, the hash() method calculates a polynomial rolling hash using the formula:

H = (c₁ × base^(n-1) + c₂ × base^(n-2) + ... + cₙ × base^0) mod prime

Where c represents character codes and base is a constant (typically 31 or 101). This value is stored as wordHash in the driver file src/algorithms/string/rabin-karp/rabinKarp.js.

The Sliding Window Initialization

The algorithm initializes a window of length equal to the pattern (word.length) at the start of the text. It computes the hash for this initial window using the same PolynomialHash.hash() method. Subsequent windows reuse this calculation rather than starting over.

O(1) Hash Updates with roll()

For each subsequent position, the PolynomialHash.roll() method updates the hash in constant time. The method signature accepts three parameters:

• prevHash – the hash value of the previous window
• prevFrame – the substring of the previous window
• currentFrame – the new substring after shifting one character right

The implementation removes the contribution of the leftmost character, multiplies the intermediate result by the base, adds the new rightmost character's value, and applies the modulus operation. This arithmetic allows the algorithm to maintain the polynomial representation without iterating through all characters again.

Collision Detection and Verification

When currentFrameHash equals wordHash, the algorithm performs a final exact-string comparison (text.substr(charIndex, word.length) === word) to guard against hash collisions. If the strings match, the current index is returned; otherwise, the search continues.

Source Code Implementation Details

The implementation spans two primary files that separate concerns between the search logic and the mathematical hashing operations.

src/algorithms/string/rabin-karp/rabinKarp.js contains the driver logic that orchestrates the search. It imports PolynomialHash, hashes the pattern, iterates through the text using a sliding window, and calls the rolling hash update for each shift.

src/algorithms/cryptography/polynomial-hash/PolynomialHash.js implements the PolynomialHash class with two critical methods:

• hash(frame) – computes the initial polynomial hash for a string
• roll(prevHash, prevFrame, currentFrame) – computes the next hash value in O(1) time by incorporating only the characters that exit and enter the window

Practical Code Examples

The following example demonstrates basic usage of the Rabin-Karp implementation:

import rabinKarp from './src/algorithms/string/rabin-karp/rabinKarp.js';

const text = 'The quick brown fox jumps over the lazy dog';
const word = 'brown';

const index = rabinKarp(text, word);
console.log(index); // → 10

For advanced scenarios requiring direct hash manipulation, you can use the PolynomialHash class to roll hashes manually:

import PolynomialHash from './src/algorithms/cryptography/polynomial-hash/PolynomialHash.js';

const hasher = new PolynomialHash();
const pattern = 'hello';
const patternHash = hasher.hash(pattern);

const text = 'hello world';
let window = text.slice(0, pattern.length);
let windowHash = hasher.hash(window);

for (let i = 0; i <= text.length - pattern.length; i++) {
  if (i > 0) {
    const prevWindow = text.slice(i - 1, i - 1 + pattern.length);
    const nextWindow = text.slice(i, i + pattern.length);
    windowHash = hasher.roll(windowHash, prevWindow, nextWindow);
    window = nextWindow;
  }

  if (windowHash === patternHash && window === pattern) {
    console.log('Match found at index:', i);
    break;
  }
}

Summary

• The Rabin-Karp algorithm achieves O(N + M) time complexity by hashing the pattern once and updating window hashes in constant time using the rolling hash technique.
• The PolynomialHash.roll() method in src/algorithms/cryptography/polynomial-hash/PolynomialHash.js performs O(1) arithmetic operations to slide the hash window, removing the leftmost character and adding the new rightmost character.
• Hash collisions are mitigated through exact string comparison only when hash values match, ensuring correctness while maintaining performance.
• The implementation separates concerns between the search driver (rabinKarp.js) and the mathematical hashing logic (PolynomialHash.js), making the rolling hash reusable for other cryptographic or string-processing applications.

Frequently Asked Questions

What is the time complexity advantage of using a rolling hash in Rabin-Karp?

Without a rolling hash, comparing every substring of length M to a pattern would require O(N × M) character comparisons. The rolling hash reduces this to O(N + M) because the pattern is hashed once in O(M) time, and each of the N window positions updates its hash in O(1) time using the roll() method.

How does the algorithm handle hash collisions?

When the hash of a text window matches the pattern hash, the algorithm performs a direct string comparison (text.substr(charIndex, word.length) === word) to verify the match. This collision check ensures that false positives caused by different strings producing identical hash values do not return incorrect indices.

Can the rolling hash implementation detect multiple pattern occurrences?

Yes. The current implementation in src/algorithms/string/rabin-karp/rabinKarp.js can be modified to collect all matching indices rather than returning after the first match. Because the rolling hash computes values for every window position independently, detecting multiple occurrences maintains the same O(N + M) complexity regardless of how many matches exist.

Why does the implementation use polynomial hashing specifically?

Polynomial hashing distributes string values uniformly across the hash space and allows mathematical decomposition. When removing the leftmost character c from a window of length L, the implementation subtracts c × base^(L-1), then multiplies the remainder by the base, and adds the new rightmost character. This algebraic property makes O(1) rolling possible, whereas simpler hash functions like sum-of-characters would not support efficient removal of the leftmost contribution.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}