Rabin Karp String Matching in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the hash value for the pattern.

DSA C

int pattern_hash = 0;
for (int i = 0; i < m; i++) {
    pattern_hash = (pattern_hash * d + pattern[i]) % [1];
}

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

Aq

Bm

Cd

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Using the length of the pattern or text instead of the modulus.

Using the base d as modulus.

The modulus q is used to keep the hash values within a manageable range to avoid overflow.

2fill in blank

medium

Complete the code to compute the initial hash value for the text window.

DSA C

int text_hash = 0;
for (int i = 0; i < m; i++) {
    text_hash = (text_hash * d + text[i]) % [1];
}

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

An

Bd

Cm

Dq

Attempts:

3 left

💡 Hint

Common Mistakes

Using the length of the pattern or text instead of the modulus.

Using the base d as modulus.

The modulus q is used to keep the hash values within a manageable range to avoid overflow.

3fill in blank

hard

Fix the error in updating the rolling hash when sliding the window.

DSA C

text_hash = (d * (text_hash - text[i] * [1]) + text[i + m]) % q;
if (text_hash < 0) {
    text_hash += q;
}

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

Apow(d, m)

Bm

Ch

Dq

Attempts:

3 left

💡 Hint

Common Mistakes

Using pow(d, m) directly without modulus.

Using the modulus q instead of h.

The variable h stores the value of (d^(m-1)) % q, used to remove the leading character's contribution.

4fill in blank

hard

Fill both blanks to check for pattern match after hash match.

DSA C

if (pattern_hash == text_hash) {
    int j = 0;
    while (j < m && pattern[j] == text[i + j]) {
        j[1]1;
    }
    if (j == [2]) {
        printf("Pattern found at index %d\n", i);
    }
}

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

A+=

B-=

Cm

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Using '-=' instead of '+=' for increment.

Comparing j to text length instead of pattern length.

We increment j by 1 to check each character, and compare j to m, the pattern length, to confirm full match.

5fill in blank

hard

Fill all three blanks to compute the value of h used in rolling hash.

DSA C

int h = 1;
for (int i = 0; i < [3] - 1; i++) {
    h = (h * [1]) % [2];
}

// h is used to remove leading digit

// d is the number of characters in input alphabet
// q is a prime number

// m is the length of the pattern

// Compute initial hashes and slide the pattern over text

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

Ad

Bq

Cm

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong variables for multiplication or modulus.

Looping incorrect number of times.

h is computed as (d^(m-1)) % q, so we multiply h by d and take modulus q in each iteration for m-1 times.