✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-198

Rabin-Karp Algorithm

Learn how Rabin-Karp uses hash values and a rolling hash technique to search for a pattern efficiently across a larger text.

Explanation

Overview

The Rabin-Karp algorithm is a string-searching algorithm that uses hashing to compare a pattern with text windows. It calculates a hash value for the pattern and for text substrings of the same length. When the hash values match, it performs a direct character comparison to verify the match, because different strings can produce the same hash.

Key concepts

Hash functions; Polynomial rolling hash; Sliding window; Hash collision; Modular arithmetic; Character verification

Variables

text: The larger string being searched.; pattern: The pattern to find.; m: The length of the pattern.; base: The numerical base used in the polynomial hash.; q: A modulus used to keep hash values within a manageable range.; hash: The numerical value representing a string window.

Complexity

averageExpected: O(n + m) under suitable hashing assumptions and a low collision rate.; worstCase: O(nm) when many hash collisions require repeated character verification.; preprocessing: O(m) to calculate the initial pattern hash.; space: O(1) auxiliary space for a single rolling window, excluding stored match positions.

Example

text: ABCCDDAEFG; pattern: CDD; explanation: The algorithm calculates the hash of CDD and compares it with the hash of each three-character window in the text. When a hash matches, it verifies the actual characters to avoid accepting a collision.; result: Pattern found at index 3 using zero-based indexing.

Pseudocode

function rabinKarp(text, pattern):
n = length(text)
m = length(pattern)
if m > n:
return []
patternHash = calculateHash(pattern)
windowHash = calculateHash(text[0 to m - 1])
matches = []
for i = 0 to n - m:
if patternHash == windowHash:
if text[i to i + m - 1] == pattern:
matches.append(i)
if i < n - m:
windowHash = calculateRollingHash(windowHash, text[i], text[i + m])
return matches

Applications

Plagiarism detection.; Multiple-pattern searching.; Document comparison.; Duplicate substring detection.; Large text processing.

Variables

Text

The larger string being searched.

Pattern

The pattern to find.

M

The length of the pattern.

Base

The numerical base used in the polynomial hash.

Q

A modulus used to keep hash values within a manageable range.

Hash

The numerical value representing a string window.

Window

A text substring whose length equals the pattern length.

Example or application

Text

ABCCDDAEFG

Pattern

CDD

Explanation

The algorithm calculates the hash of CDD and compares it with the hash of each three-character window in the text. When a hash matches, it verifies the actual characters to avoid accepting a collision.

Result

Pattern found at index 3 using zero-based indexing.

Definition

The Rabin-Karp algorithm is a string-searching algorithm that uses hashing to compare a pattern with text windows. It calculates a hash value for the pattern and for text substrings of the same length. When the hash values match, it performs a direct character comparison to verify the match, because different strings can produce the same hash.

Mathematical Representation

H_next = ((H_current - outgoingCharacter × base^(m-1)) × base + incomingCharacter) mod q.

Algorithm Steps

  • Choose a hash function and modulus.

  • Calculate the hash value of the pattern.

  • Calculate the hash value of the first text window of equal length.

  • Compare the two hash values.

  • If the hashes match, compare the actual characters.

  • Use rolling hash to calculate the next window hash efficiently.

  • Repeat until all possible text windows have been checked.

Pseudocode

function rabinKarp(text, pattern):
n = length(text)
m = length(pattern)
if m > n:
return []
patternHash = calculateHash(pattern)
windowHash = calculateHash(text[0 to m - 1])
matches = []
for i = 0 to n - m:
if patternHash == windowHash:
if text[i to i + m - 1] == pattern:
matches.append(i)
if i < n - m:
windowHash = calculateRollingHash(windowHash, text[i], text[i + m])
return matches

Complexity

Average Expected

O(n + m) under suitable hashing assumptions and a low collision rate.

Worst Case

O(nm) when many hash collisions require repeated character verification.

Preprocessing

O(m) to calculate the initial pattern hash.

Space

O(1) auxiliary space for a single rolling window, excluding stored match positions.

Key Concepts

  • Hash functions

  • Polynomial rolling hash

  • Sliding window

  • Hash collision

  • Modular arithmetic

  • Character verification

Advantages

  • Can search for multiple patterns using related hashing techniques.

  • Rolling hash makes successive window calculations efficient.

  • Useful for detecting repeated substrings.

  • Has good expected performance for suitable hash parameters.

Limitations

  • Hash collisions can cause additional character comparisons.

  • Worst-case time complexity can be O(nm).

  • The hash function and modulus must be selected carefully.

  • A hash match alone does not prove that two strings are equal.

Applications

  • Plagiarism detection.

  • Multiple-pattern searching.

  • Document comparison.

  • Duplicate substring detection.

  • Large text processing.

Related Topics

  • String Hashing

  • Rolling Hash

  • Naive Pattern Matching

  • KMP Algorithm

  • Boyer-Moore Algorithm

Practice Question

Why does Rabin-Karp verify characters after finding equal hash values?

Practice Answer

Because two different strings can produce the same hash value due to a hash collision.

Learning Objectives

  • Explain the central idea and purpose of rabin-karp algorithm.

  • Identify the assumptions, inputs, and conditions relevant to rabin-karp algorithm.

  • Evaluate an application of rabin-karp algorithm for correctness and practical resource requirements.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • String Algorithms and Pattern Matching

Suggest a correction or source · More in Algorithms & Data Structures