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.

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