Rabin Karp String Matching in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Rabin Karp hash calculation

What is the output of the following code that calculates the initial hash values for pattern and text window?

DSA Python

def initial_hash(s, length, base=256, mod=101):
    h = 0
    for i in range(length):
        h = (h * base + ord(s[i])) % mod
    return h

pattern = "abc"
text = "abcd"
pattern_hash = initial_hash(pattern, len(pattern))
text_hash = initial_hash(text, len(pattern))
print(pattern_hash, text_hash)

A 87 88

B 94 95

C 89 90

D 85 86

💡 Hint

Calculate hash by multiplying previous hash by base and adding ASCII value, then mod by 101.

The hash is calculated by iterating over each character, multiplying the current hash by 256, adding the ASCII value of the character, and taking modulo 101. For 'abc' and 'abc' in 'abcd', the hashes are 87 and 88 respectively.

❓ Predict Output

intermediate

Rabin Karp rolling hash update output

What is the output of the rolling hash update after sliding the window by one character?

DSA Python

def rolling_hash(old_hash, left_char, right_char, base=256, mod=101, pattern_len=3):
    h = old_hash - ord(left_char) * (base ** (pattern_len - 1))
    h = (h * base + ord(right_char)) % mod
    return h

old_hash = 88
new_hash = rolling_hash(old_hash, 'a', 'd')
print(new_hash)

A 23

B 25

C 24

D 26

💡 Hint

Subtract left char's weighted value, multiply by base, add new char, then mod.

The rolling hash removes the leftmost character's contribution, shifts the hash, adds the new character, and takes modulo 101. The result is 24.

🧠 Conceptual

advanced

Why use modulo in Rabin Karp hashing?

Why do we use modulo operation in the Rabin Karp hashing algorithm?

A To increase the hash value exponentially

B To keep hash values within a fixed range and avoid integer overflow

C To convert characters to ASCII values

D To sort the pattern and text before matching

💡 Hint

Think about large numbers and computer memory limits.

Modulo keeps hash values within a manageable range to prevent overflow and reduce collisions.

🔧 Debug

advanced

Identify the error in this Rabin Karp implementation snippet

What error will this code produce when running the Rabin Karp algorithm?

DSA Python

def rabin_karp_search(text, pattern):
    base = 256
    mod = 101
    m = len(pattern)
    n = len(text)
    hpattern = 0
    htext = 0
    h = 1

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

    for i in range(m):
        hpattern = (base * hpattern + ord(pattern[i])) % mod
        htext = (base * htext + ord(text[i])) % mod

    for i in range(n - m + 1):
        if hpattern == htext:
            if text[i:i+m] == pattern:
                return i
        if i < n - m:
            htext = (base * (htext - ord(text[i]) * h) + ord(text[i+m])) % mod
    return -1

print(rabin_karp_search("hello", "ll"))

A Returns 2

B Returns -1

C TypeError

D IndexError

💡 Hint

Check the loop ranges and hash updates carefully.

The code correctly finds 'll' starting at index 2 in 'hello'. No errors occur.

🚀 Application

expert

Number of hash comparisons in worst case

In the worst case, how many hash comparisons does the Rabin Karp algorithm perform when searching a pattern of length m in a text of length n?

A O(n - m + 1)

B O(n * m * log m)

C O(1)

D O(m * (n - m + 1))

💡 Hint

Consider when many hash collisions happen and substring checks occur.

In worst case, many hash collisions cause substring checks for each window, leading to O(m*(n-m+1)) comparisons.

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