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.