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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Rabin Karp hash calculation

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

DSA C

int prime = 101;
int d = 256;
int pattern_len = 3;
char pattern[] = "abc";
char text[] = "abcd";

int pattern_hash = 0, text_hash = 0, h = 1;

for (int i = 0; i < pattern_len - 1; i++)
    h = (h * d) % prime;

for (int i = 0; i < pattern_len; i++) {
    pattern_hash = (d * pattern_hash + pattern[i]) % prime;
    text_hash = (d * text_hash + text[i]) % prime;
}

printf("%d %d %d", pattern_hash, text_hash, h);

A 7 6 15

B 6 7 16

C 5 6 15

D 6 6 16

💡 Hint

Calculate hash step by step using modulo arithmetic with prime 101.

The hash for 'abc' and 'abc' substring in text both compute to 6 with base 256 and modulo 101. The value h is d^(pattern_len-1) mod prime = 256^2 mod 101 = 16.

❓ Predict Output

intermediate

Rabin Karp rolling hash update output

What is the output of the rolling hash update step in Rabin Karp for the given text and pattern?

DSA C

int prime = 101;
int d = 256;
int pattern_len = 3;
char text[] = "abcd";

int h = 16; // precomputed as 256^(3-1) % 101
int text_hash = 6; // hash of 'abc'

// Update hash to next substring 'bcd'
text_hash = (d * (text_hash - text[0] * h) + text[3]) % prime;
if (text_hash < 0) text_hash += prime;

printf("%d", text_hash);

A 7

B 6

C 8

D 5

💡 Hint

Apply the rolling hash formula carefully and adjust for negative values.

The rolling hash removes the contribution of 'a' (text[0]) and adds 'd' (text[3]). The result modulo 101 is 7.

🧠 Conceptual

advanced

Why use a prime number in Rabin Karp hashing?

Why is a prime number used as the modulus in the Rabin Karp hashing algorithm?

A To reduce the chance of hash collisions by distributing hash values uniformly

B To make the hash calculation faster by using prime arithmetic

C To ensure the hash values are always positive integers

D To simplify the rolling hash update formula

💡 Hint

Think about how prime modulus affects hash distribution.

Using a prime modulus helps spread hash values more evenly, reducing collisions and improving matching accuracy.

🔧 Debug

advanced

Identify the error in this Rabin Karp substring search snippet

What error will this code snippet cause when searching for pattern in text using Rabin Karp?

DSA C

int prime = 101;
int d = 256;
int pattern_len = 3;
char pattern[] = "abc";
char text[] = "abcd";

int pattern_hash = 0, text_hash = 0, h = 1;

for (int i = 0; i < pattern_len - 1; i++)
    h = (h * d) % prime;

for (int i = 0; i < pattern_len; i++) {
    pattern_hash = (d * pattern_hash + pattern[i]) % prime;
    text_hash = (d * text_hash + text[i]) % prime;
}

for (int i = 0; i <= strlen(text) - pattern_len; i++) {
    if (pattern_hash == text_hash) {
        for (int j = 0; j < pattern_len; j++) {
            if (text[i + j] != pattern[j])
                break;
            if (j == pattern_len - 1)
                printf("Pattern found at index %d", i);
        }
    }
    if (i < strlen(text) - pattern_len) {
        text_hash = (d * (text_hash - text[i] * h) + text[i + pattern_len]) % prime;
        if (text_hash < 0) text_hash += prime;
    }
}

A The break statement only exits the inner loop, causing incorrect matches

B The inner loop may print multiple times for the same index

C The code may access text out of bounds when updating text_hash

D The pattern_hash is not computed correctly

💡 Hint

Check when the print statement executes inside the inner loop.

The print statement is inside the inner loop and can execute multiple times if characters match partially, causing repeated prints for the same index.

🚀 Application

expert

Number of hash comparisons in worst case for Rabin Karp

Given a text of length N and a pattern of length M, what is the worst-case number of hash comparisons Rabin Karp algorithm performs?

A O(N - M + 1)

B O(N * M)

C O(M * (N - M + 1))

D O(1)

💡 Hint

Consider the worst case when many hash collisions occur.

In worst case, many hash collisions cause character-by-character checks for each substring, leading to O(M * (N - M + 1)) comparisons.