Rabin Karp String Matching in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to calculate the initial hash value of the pattern.

DSA Python

pattern_hash = 0
for i in range(len(pattern)):
    pattern_hash = (pattern_hash * base + ord(pattern[i])) % [1]

Drag options to blanks, or click blank then click option'

Aprime

Blen(text)

C256

Dlen(pattern)

Attempts:

3 left

💡 Hint

Common Mistakes

Using length of text or pattern as modulus causes more collisions.

The modulus is usually a large prime number to reduce collisions in hashing.

2fill in blank

medium

Complete the code to update the rolling hash when sliding the window by one character.

DSA Python

text_hash = (text_hash - ord(text[i]) * high_order) * base + ord(text[i + len(pattern)])
text_hash = text_hash % [1]

Drag options to blanks, or click blank then click option'

Alen(text)

Bprime

C256

Dlen(pattern)

Attempts:

3 left

💡 Hint

Common Mistakes

Using different modulus causes incorrect hash comparisons.

The modulus must be the same prime number used for initial hashing to keep hash values consistent.

3fill in blank

hard

Fix the error in the condition that checks if the current window matches the pattern.

DSA Python

if pattern_hash == text_hash and text[i:i+len(pattern)] == [1]:

Drag options to blanks, or click blank then click option'

Apattern[::-1]

Btext_hash

Cpattern

Dtext[i+1:i+len(pattern)+1]

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with reversed pattern or hash value instead of substring.

We compare the current substring in text with the pattern to confirm a match after hash match.

4fill in blank

hard

Fill both blanks to compute the highest order multiplier and initialize the base value.

DSA Python

base = [1]
high_order = pow(base, len(pattern) - 1, [2])

Drag options to blanks, or click blank then click option'

A256

Blen(pattern)

Cprime

Dlen(text)

Attempts:

3 left

💡 Hint

Common Mistakes

Using length of pattern or text as base or modulus.

Base is usually 256 for ASCII characters, and modulus is the prime number used for hashing.

5fill in blank

hard

Fill all three blanks to complete the main loop that slides over the text and checks for matches.

DSA Python

for i in range(len(text) - len(pattern) + 1):
    if pattern_hash == text_hash and text[i:i+len(pattern)] == [1]:
        result.append(i)
    if i < len(text) - len(pattern):
        text_hash = (text_hash - ord(text[i]) * [2]) * [3] + ord(text[i + len(pattern)])
        text_hash %= prime

Drag options to blanks, or click blank then click option'

Apattern

Bhigh_order

Cbase

Dtext

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong variables for substring, high_order, or base in hash update.

The loop compares substring with pattern, updates hash by removing old char multiplied by high_order, multiplies by base, adds new char, and applies modulus.