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 C++ code that calculates the initial hash values for pattern and text substring using Rabin Karp algorithm?

DSA C++

const int d = 256;
const int q = 101;

int calculateHash(const std::string &str, int length) {
    int hash = 0;
    for (int i = 0; i < length; i++) {
        hash = (d * hash + str[i]) % q;
    }
    return hash;
}

int main() {
    std::string pattern = "abc";
    std::string text = "abcd";
    int pHash = calculateHash(pattern, pattern.size());
    int tHash = calculateHash(text, pattern.size());
    std::cout << pHash << " " << tHash << std::endl;
    return 0;
}

A 6 6

B 90 90

C 94 95

D 6 7

💡 Hint

Calculate hash using formula: hash = (d * previous_hash + current_char) % q for each character.

The hash for 'abc' and 'abc' substring in 'abcd' both compute to 90 using the given formula with d=256 and q=101.

🧠 Conceptual

intermediate

Understanding rolling hash update in Rabin Karp

In Rabin Karp algorithm, when moving the window by one character in the text, how is the rolling hash updated efficiently?

A Multiply the old hash by the new character's ASCII value.

B Recalculate the hash from scratch for the new substring.

C Add the new character's ASCII value to the hash without removing the old character.

D Remove the old character's contribution, multiply hash by base, add new character, then take modulo.

💡 Hint

Think about how to avoid recomputing the entire hash for each substring.

The rolling hash removes the contribution of the old character, shifts the hash by multiplying with base, adds the new character, and takes modulo to keep hash within range.

🔧 Debug

advanced

Identify the error in Rabin Karp substring search code

What error will the following C++ code produce when searching for pattern "abc" in text "ababc" using Rabin Karp?

DSA C++

const int d = 256;
const int q = 101;

int main() {
    std::string text = "ababc";
    std::string pattern = "abc";
    int n = text.size();
    int m = pattern.size();
    int pHash = 0, tHash = 0, h = 1;

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

    for (int i = 0; i < m; i++) {
        pHash = (d * pHash + pattern[i]) % q;
        tHash = (d * tHash + text[i]) % q;
    }

    for (int i = 0; i <= n - m; i++) {
        if (pHash == tHash) {
            bool match = true;
            for (int j = 0; j < m; j++) {
                if (text[i + j] != pattern[j]) {
                    match = false;
                    break;
                }
            }
            if (match) {
                std::cout << "Pattern found at index " << i << std::endl;
            }
        }
        if (i < n - m) {
            tHash = (d * (tHash - text[i] * h) + text[i + m]) % q;
            if (tHash < 0) tHash += q;
        }
    }
    return 0;
}

A Pattern found at index 2

B No output, pattern not found

C Runtime error due to negative hash value

D Pattern found at index 1 and 2

💡 Hint

Check the substring matches and hash updates carefully.

The pattern "abc" appears starting at index 2 in "ababc". The code correctly finds it once at index 2.

🚀 Application

advanced

Number of pattern occurrences using Rabin Karp

Given text "aaaaa" and pattern "aa", how many times will the Rabin Karp algorithm find the pattern in the text?

A 2

B 3

C 4

D 5

💡 Hint

Count overlapping occurrences of the pattern in the text.

Pattern "aa" appears starting at indices 0,1,2,3 in "aaaaa", total 4 times including overlaps.

🧠 Conceptual

expert

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

Why does the Rabin Karp algorithm use a prime number as the modulus (q) in its hash calculations?

A To reduce the chance of hash collisions and ensure uniform distribution of hash values.

B Because prime numbers make the hash calculation faster.

C To guarantee that the hash values are always positive.

D Because prime numbers simplify the rolling hash update formula.

💡 Hint

Think about how modulus affects hash distribution and collisions.

Using a prime modulus reduces collisions by distributing hash values more uniformly, improving algorithm accuracy.

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 Rabin Karp's approach

   The algorithm uses a hash function to convert the pattern and text substrings into numbers.

2. Step 2: Use hashing for efficient matching

   By comparing hash values instead of characters, it quickly finds potential matches and then verifies them.

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
• Assuming it sorts strings before matching
• Confusing it with recursive search methods

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. Add leftmost char's hash, multiply by base, subtract new char's hash

B. Multiply entire hash by base and add new char's hash only

C. Remove leftmost char's hash, multiply by base, add new char's hash

D. Recalculate hash from scratch for new substring

Solution

1. Step 1: Understand rolling hash update

   Remove the leftmost character's contribution, multiply remaining hash by base, then add new character's value.

2. Step 2: Apply formula for next substring

   This keeps hash calculation efficient without recomputing from scratch.

3. Final Answer:

   Remove leftmost char's hash, multiply by base, add new char's hash -> Option C

4. Quick Check:

   Rolling hash update = Remove + multiply + add [OK]

Hint: Rolling hash = remove old char + shift + add new char [OK]

Common Mistakes:

• Recalculating hash fully each time
• Adding instead of removing old char's hash
• Multiplying after adding new char instead of before

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

std::string text = "ababc";
std::string pattern = "abc";
// Assume correct Rabin Karp implementation
std::vector<int> matches = rabinKarpSearch(text, pattern);
for (int pos : matches) std::cout << pos << " ";

medium

A. 1

B. 0 2

C. No output

D. 2

Solution

1. Step 1: Identify pattern occurrences in text

   Pattern "abc" appears starting at index 2 in "ababc" (0-based indexing).

2. Step 2: Confirm no other matches

   Substring at index 0 is "aba", not "abc"; index 1 is "bab", not "abc".

3. Final Answer:

   2 -> Option D

4. Quick Check:

   Pattern found at index 2 [OK]

Hint: Check substring positions carefully for exact matches [OK]

Common Mistakes:

• Assuming match at index 0 incorrectly
• Confusing overlapping substrings
• Using 1-based indexing instead of 0-based

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

hash = (hash - text[i] * pow(base, m-1)) * base + text[i+m];

What is the likely problem?

medium

A. Missing modulo operation causing overflow

B. Wrong power used in subtraction term

C. Adding instead of subtracting old char's hash

D. Incorrect base multiplier order

Solution

1. Step 1: Check arithmetic operations in rolling hash

   The formula subtracts old char's hash, multiplies by base, adds new char's value.

2. Step 2: Identify missing modulo usage

   Without modulo, hash values can overflow integer limits causing wrong results.

3. Final Answer:

   Missing modulo operation causing overflow -> Option A

4. Quick Check:

   Modulo needed to prevent overflow [OK]

Hint: Always apply modulo after each hash update [OK]

Common Mistakes:

• Ignoring modulo leading to wrong hash values
• Using wrong power exponent
• Mixing addition and subtraction signs

5. Given a large text and multiple patterns, how can Rabin Karp be adapted to efficiently find all pattern occurrences?

hard

A. Use a combined hash set of all patterns and check text substrings against it

B. Run Rabin Karp separately for each pattern on the entire text

C. Sort all patterns and use binary search on text substrings

D. Use recursion to match patterns one by one

Solution

1. Step 1: Understand multi-pattern matching challenge

   Running Rabin Karp separately for each pattern is inefficient for many patterns.

2. Step 2: Use combined hashing approach

   Hash all patterns and store in a set. Then slide over text, hashing substrings and checking set membership.

3. Step 3: Efficiently find all matches

   This reduces repeated work and speeds up multi-pattern search.

4. Final Answer:

   Use a combined hash set of all patterns and check text substrings against it -> Option A

5. Quick Check:

   Combined hashing = efficient multi-pattern search [OK]

Hint: Hash all patterns once, then check text substrings [OK]

Common Mistakes:

• Running separate searches for each pattern
• Sorting patterns instead of hashing
• Using recursion unnecessarily