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.

Practice

1. What is the main idea behind the Rabin Karp String Matching algorithm?

easy

A. Compare each character one by one without hashing

B. Use hashing to find pattern matches efficiently

C. Sort the text and pattern before matching

D. Use recursion to find all pattern occurrences

Solution

1. Step 1: Understand the algorithm's approach

   Rabin Karp uses hashing to convert strings into numbers for quick comparison.

2. Step 2: Compare hash values instead of characters

   It compares hash values of the pattern and text substrings to find matches efficiently.

3. Final Answer:

   Use hashing to find pattern matches efficiently -> Option B

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 always
• Confusing with brute force matching
• Assuming sorting is involved

2. Which of the following is the correct way to update the rolling hash in Rabin Karp when moving from substring s[i..i+m-1] to s[i+1..i+m]?

easy

A. hash = (hash * base) + s[i] - s[i+m]

B. hash = (hash + s[i] * power) * base - s[i+m]

C. hash = (hash - s[i] * power) * base + s[i+m]

D. hash = (hash - s[i+m] * power) + s[i]

Solution

1. Step 1: Understand rolling hash update formula

   Remove the leftmost character's weighted value, multiply by base, add new character.

2. Step 2: Apply formula to substring shift

   hash = (hash - s[i] * power) * base + s[i+m] correctly updates the hash.

3. Final Answer:

   hash = (hash - s[i] * power) * base + s[i+m] -> Option C

4. Quick Check:

   Remove left char, multiply, add right char [OK]

Hint: Subtract old char, multiply hash, add new char [OK]

Common Mistakes:

• Adding instead of subtracting old char
• Wrong order of operations
• Mixing indices of characters

3. What will be the output of the following C code snippet using Rabin Karp to find pattern "abc" in text "ababc"?

#include 
#include 
#define base 256
#define prime 101

int main() {
    char text[] = "ababc";
    char pattern[] = "abc";
    int n = strlen(text), m = strlen(pattern);
    int p = 0, t = 0, h = 1, i, j;

    for (i = 0; i < m-1; i++)
        h = (h * base) % prime;

    for (i = 0; i < m; i++) {
        p = (base * p + pattern[i]) % prime;
        t = (base * t + text[i]) % prime;
    }

    for (i = 0; i <= n - m; i++) {
        if (p == t) {
            for (j = 0; j < m; j++) {
                if (text[i+j] != pattern[j])
                    break;
            }
            if (j == m)
                printf("Pattern found at index %d\n", i);
        }
        if (i < n - m) {
            t = (base * (t - text[i] * h) + text[i + m]) % prime;
            if (t < 0) t = t + prime;
        }
    }
    return 0;
}

medium

A. Pattern found at index 2

B. Pattern found at index 0

C. Pattern found at index 1

D. No pattern found

Solution

1. Step 1: Calculate initial hashes and check first substring

   Pattern "abc" hash matches substring "aba" at index 0? No, characters differ.

2. Step 2: Slide window and check next substring

   At index 1, substring "bab" hash differs. At index 2, substring "abc" matches pattern exactly.

3. Final Answer:

   Pattern found at index 2 -> Option A

4. Quick Check:

   Match at index 2 = Pattern found at index 2 [OK]

Hint: Check hash then verify substring match [OK]

Common Mistakes:

• Assuming match at index 0 without verification
• Ignoring negative hash correction
• Not verifying characters after hash match

4. Identify the bug in this Rabin Karp hash update snippet:

t = (base * (t - text[i] * h) + text[i + m]) % prime;
if (t < 0) t = t - prime;

medium

A. Should add prime instead of subtracting when t < 0

B. Multiplication order is wrong

C. Index i + m is out of range

D. No bug, code is correct

Solution

1. Step 1: Understand negative hash correction

   If hash becomes negative after modulo, add prime to keep it positive.

2. Step 2: Check given code's correction

   Code subtracts prime when t < 0, which makes t more negative. It should add prime.

3. Final Answer:

   Should add prime instead of subtracting when t < 0 -> Option A

4. Quick Check:

   Negative hash fix = add prime [OK]

Hint: Add prime if hash is negative after modulo [OK]

Common Mistakes:

• Subtracting prime instead of adding
• Ignoring negative hash values
• Confusing modulo operation behavior

5. You want to find all occurrences of pattern "aaa" in text "aaaaaa" using Rabin Karp. How many matches will the algorithm report and why?

hard

A. 0 matches, because pattern length equals text length

B. 3 matches, because only non-overlapping occurrences count

C. 1 match, because repeated characters cause hash collision

D. 4 matches, because overlapping occurrences are counted

Solution

1. Step 1: Count possible substrings of length 3 in text

   Text length 6, pattern length 3, so 6 - 3 + 1 = 4 substrings.

2. Step 2: Check each substring for pattern match

   All substrings "aaa" at indices 0,1,2,3 match pattern including overlaps.

3. Final Answer:

   4 matches, because overlapping occurrences are counted -> Option D

4. Quick Check:

   Overlapping matches counted = 4 [OK]

Hint: Count all substrings including overlaps [OK]

Common Mistakes:

• Ignoring overlapping matches
• Assuming only non-overlapping matches count
• Confusing hash collisions with matches