Rabin Karp String Matching in DSA Python

Mental Model

We use a rolling number code for each part of the text to quickly find where the pattern matches. Instead of checking every letter, we compare these codes.

Analogy: Imagine you want to find a word in a book by checking the sum of letter values instead of reading every letter. If the sums match, you check the word carefully.

Text:  T -> h -> i -> s ->   -> i -> s ->   -> a ->   -> t -> e -> x -> t -> null
Pattern:       ↑   ↑   ↑   ↑
Hash window:  [hash of 'This']

Dry Run Walkthrough

Input: text: 'abababc', pattern: 'abc'

Goal: Find the starting index where 'abc' appears in 'abababc' using rolling hash

Step 1: Calculate hash for pattern 'abc' and first window 'aba' in text

pattern_hash=hash('abc'), window_hash=hash('aba')

Why: We need initial hashes to start comparing pattern with text windows

Step 2: Compare pattern_hash and window_hash; they differ, slide window by 1

window moves to 'bab', window_hash updated using rolling hash

Why: Hashes differ, so pattern not found at index 0; move forward

Step 3: Compare pattern_hash and window_hash for 'bab'; differ again, slide window

window moves to 'aba', window_hash updated

Why: Still no match, continue sliding window

Step 4: Compare pattern_hash and window_hash for 'aba'; differ, slide window

window moves to 'bab', window_hash updated

Why: No match, keep sliding

Step 5: Compare pattern_hash and window_hash for 'bab'; differ, slide window

window moves to 'abc', window_hash updated

Why: Last window to check

Step 6: pattern_hash equals window_hash for 'abc', verify characters match

Match found at index 4

Why: Hashes match, so check actual characters to confirm pattern found

Result:

Final state: Match found at index 4

Annotated Code

DSA Python

class RabinKarp:
    def __init__(self, base=256, prime=101):
        self.base = base
        self.prime = prime

    def search(self, text: str, pattern: str) -> int:
        n, m = len(text), len(pattern)
        if m > n:
            return -1

        pattern_hash = 0
        window_hash = 0
        h = 1  # base^(m-1) % prime

        for i in range(m - 1):
            h = (h * self.base) % self.prime

        for i in range(m):
            pattern_hash = (self.base * pattern_hash + ord(pattern[i])) % self.prime
            window_hash = (self.base * window_hash + ord(text[i])) % self.prime

        for i in range(n - m + 1):
            if pattern_hash == window_hash:
                if text[i:i + m] == pattern:
                    return i
            if i < n - m:
                window_hash = (self.base * (window_hash - ord(text[i]) * h) + ord(text[i + m])) % self.prime
                if window_hash < 0:
                    window_hash += self.prime
        return -1


if __name__ == '__main__':
    rk = RabinKarp()
    text = 'abababc'
    pattern = 'abc'
    index = rk.search(text, pattern)
    if index != -1:
        print(f'Pattern found at index {index}')
    else:
        print('Pattern not found')

for i in range(m - 1): h = (h * self.base) % self.prime

Calculate the high order digit multiplier for rolling hash

for i in range(m): pattern_hash = (self.base * pattern_hash + ord(pattern[i])) % self.prime window_hash = (self.base * window_hash + ord(text[i])) % self.prime

Compute initial hash values for pattern and first text window

if pattern_hash == window_hash: if text[i:i + m] == pattern: return i

Check if hashes match and verify actual substring to confirm pattern

window_hash = (self.base * (window_hash - ord(text[i]) * h) + ord(text[i + m])) % self.prime if window_hash < 0: window_hash += self.prime

Update rolling hash for next window efficiently

Output

Pattern found at index 4

Complexity Analysis

Time: O(n + m) because we compute initial hashes in O(m) and slide through text in O(n) with constant time hash updates

Space: O(1) because we use fixed extra space for hash calculations and no extra data structures

vs Alternative: Compared to naive substring search O(n*m), Rabin-Karp is faster on average by using hash comparisons to skip unnecessary checks

Edge Cases

pattern longer than text

returns -1 immediately as no match is possible

DSA Python

if m > n:
    return -1

pattern equals text

returns 0 as the pattern matches at start

DSA Python

if pattern_hash == window_hash:
    if text[i:i + m] == pattern:
        return i

pattern not in text

returns -1 after checking all windows

DSA Python

return -1

When to Use This Pattern

When you need to find a substring efficiently and want to avoid checking every character repeatedly, use Rabin-Karp because it uses rolling hashes to speed up matching.

Common Mistakes

Mistake: Not updating the rolling hash correctly when sliding the window
Fix: Subtract the old char's weighted value and add the new char, then mod prime and adjust if negative

Mistake: Comparing only hashes without verifying actual substring
Fix: Always verify substring characters when hashes match to avoid false positives

Summary

Finds a pattern in text using rolling hash to speed up substring matching

Use when you want faster substring search than naive character-by-character comparison

The key is to use a rolling hash to quickly update and compare hash values for each text window

Practice

1. What is the main idea behind the Rabin Karp String Matching algorithm?

easy

A. It uses hashing to find pattern matches efficiently.

B. It compares each character one by one without hashing.

C. It sorts the text before searching for the pattern.

D. It uses recursion to find the pattern in the text.

Solution

1. Step 1: Understand Rabin Karp's approach

   The algorithm uses a hash function to convert the pattern and text substrings into numbers.

2. Step 2: Use hashing for efficient matching

   By comparing hash values instead of characters, it quickly finds potential matches.

3. Final Answer:

   It uses hashing to find pattern matches efficiently. -> Option A

4. Quick Check:

   Hashing = Efficient matching [OK]

Hint: Remember: Rabin Karp uses hashing for fast pattern search [OK]

Common Mistakes:

• Thinking it compares characters directly without hashing
• Confusing it with sorting-based algorithms
• Assuming it uses recursion

2. Which of the following is the correct way to compute the rolling hash in Rabin Karp for the next substring?

easy

A. new_hash = old_hash * old_char + new_char

B. new_hash = old_hash + old_char - new_char

C. new_hash = (old_hash - old_char * base^(m-1)) * base + new_char

D. new_hash = old_hash / base + new_char * base^(m-1)

Solution

1. Step 1: Recall rolling hash formula

   Rolling hash removes the old char's contribution and adds the new char's value.

2. Step 2: Apply formula correctly

   It subtracts old_char * base^(m-1), multiplies by base, then adds new_char.

3. Final Answer:

   new_hash = (old_hash - old_char * base^(m-1)) * base + new_char -> Option C

4. Quick Check:

   Rolling hash formula = new_hash = (old_hash - old_char * base^(m-1)) * base + new_char [OK]

Hint: Subtract old char, multiply by base, add new char [OK]

Common Mistakes:

• Adding old_char instead of subtracting
• Dividing instead of multiplying by base
• Ignoring power of base for old_char

3. What will be the output of the following code snippet using Rabin Karp to find pattern 'abc' in text 'ababc'?

def rabin_karp(text, pattern):
    base = 256
    prime = 101
    m = len(pattern)
    n = len(text)
    pattern_hash = 0
    text_hash = 0
    h = 1

    for i in range(m-1):
        h = (h * base) % prime

    for i in range(m):
        pattern_hash = (base * pattern_hash + ord(pattern[i])) % prime
        text_hash = (base * text_hash + ord(text[i])) % prime

    for i in range(n - m + 1):
        if pattern_hash == text_hash:
            if text[i:i+m] == pattern:
                return i
        if i < n - m:
            text_hash = (base * (text_hash - ord(text[i]) * h) + ord(text[i + m])) % prime
            if text_hash < 0:
                text_hash += prime
    return -1

print(rabin_karp('ababc', 'abc'))

medium

A. 0

B. 1

C. -1

D. 2

Solution

1. Step 1: Calculate pattern and initial text hash

   Pattern 'abc' length 3, initial text substring 'aba'. Hashes differ, so move forward.

2. Step 2: Slide over text and compare hashes

   At index 1, substring 'bab' hash differs. At index 2, substring 'abc' hash matches pattern hash and strings match.

3. Final Answer:

   2 -> Option D

4. Quick Check:

   Pattern found at index 2 [OK]

Hint: Check hash then substring; match at index 2 [OK]

Common Mistakes:

• Returning first hash match without substring check
• Confusing index positions
• Ignoring negative hash adjustment

4. Identify the bug in this Rabin Karp implementation snippet:

text_hash = (base * (text_hash - ord(text[i]) * h) + ord(text[i + m])) % prime
if text_hash < 0:
    text_hash = text_hash - prime

medium

A. The negative hash correction should add prime, not subtract.

B. The subtraction of ord(text[i]) * h is incorrect.

C. The modulo operation should be done after adding prime.

D. The base should be added, not multiplied.

Solution

1. Step 1: Understand negative hash correction

   If hash is negative after modulo, add prime to make it positive.

2. Step 2: Identify incorrect operation

   Code subtracts prime instead of adding it, causing wrong hash values.

3. Final Answer:

   The negative hash correction should add prime, not subtract. -> Option A

4. Quick Check:

   Negative hash fix = add prime [OK]

Hint: Add prime if hash is negative, never subtract [OK]

Common Mistakes:

• Subtracting prime instead of adding
• Ignoring negative hash values
• Misplacing modulo operation

5. Given a large text and multiple patterns, which modification to Rabin Karp helps efficiently find all patterns in the text?

hard

A. Run Rabin Karp separately for each pattern without optimization.

B. Use a combined hash set of all patterns and check text substrings against it.

C. Sort all patterns and use binary search on text substrings.

D. Use recursion to search each pattern in the text.

Solution

1. Step 1: Understand multiple pattern search challenge

   Running Rabin Karp separately for each pattern is inefficient for many patterns.

2. Step 2: Use combined hashing approach

   Hash all patterns and store in a set. Then check each text substring's hash against this set for quick matches.

3. Final Answer:

   Use a combined hash set of all patterns and check text substrings against it. -> Option B

4. Quick Check:

   Combined hash set = efficient multi-pattern search [OK]

Hint: Hash all patterns once, check text hashes against set [OK]

Common Mistakes:

• Running separate searches for each pattern
• Sorting patterns instead of hashing
• Using recursion unnecessarily