concept · INFO-CS-ADS-198Rabin-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
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.
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