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 for the pattern "abc" using a simple rolling hash?

DSA C#

using System;

class Program {
    static void Main() {
        string pattern = "abc";
        int prime = 101;
        int hash = 0;
        int power = 1;
        for (int i = pattern.Length - 1; i >= 0; i--) {
            hash += pattern[i] * power;
            power *= prime;
        }
        Console.WriteLine(hash);
    }
}

A 999496

B 999495

C 999493

D 999494

💡 Hint

Calculate hash as sum of char codes times powers of prime starting from rightmost character.

The hash is calculated as 'c'*1 + 'b'*101 + 'a'*101^2. Using ASCII codes: 'a'=97, 'b'=98, 'c'=99. So hash = 99 + 9898 + 989497 = 999494, which is option D.

❓ Predict Output

intermediate

Rabin Karp rolling hash update output

What is the output of this C# code snippet that updates the rolling hash when sliding the window from "abc" to "bcd"?

DSA C#

using System;

class Program {
    static void Main() {
        string text = "abcd";
        int prime = 101;
        int patternLength = 3;
        int power = 1;
        for (int i = 1; i < patternLength; i++) power *= prime;

        int hash = 0;
        for (int i = 0; i < patternLength; i++) {
            hash += text[i] * (int)Math.Pow(prime, patternLength - i - 1);
        }

        // Remove 'a', add 'd'
        hash = (hash - text[0] * power) * prime + text[3];

        Console.WriteLine(hash);
    }
}

A 1009796

B 999494

C 1009797

D 1009697

💡 Hint

Use rolling hash formula: remove old char * highest power, multiply by prime, add new char.

Initial hash for "abc" is 999494. Remove 'a' * 101^2 = 97*10201=989497, so 999494 - 989497 = 9997. Multiply by 101: 9997*101=1009697. Add 'd' (100): 1009797, which is option C.

🧠 Conceptual

advanced

Why use a prime number in Rabin Karp hashing?

Why is a prime number often chosen as the base (multiplier) in the Rabin Karp rolling hash algorithm?

A Because prime numbers are faster to compute with in multiplication

B To reduce the chance of hash collisions by spreading hash values more uniformly

C To ensure the hash values are always even numbers

D Because prime numbers make the algorithm run in constant time

💡 Hint

Think about how hash values distribute over possible inputs.

Using a prime number as the base helps spread hash values more uniformly across the range, reducing collisions. It does not affect speed or guarantee even numbers or constant time.

🔧 Debug

advanced

Identify the error in this Rabin Karp implementation snippet

What error will this C# code produce when running the Rabin Karp algorithm?

DSA C#

int prime = 101;
int patternLength = 3;
int power = 1;
for (int i = 0; i < patternLength; i++) {
    power *= prime;
}
// power is used as highest power of prime

// Later in rolling hash update:
hash = (hash - text[start] * power) * prime + text[start + patternLength];

A Logical error: power is one step too large for rolling hash calculation

B OverflowException because power becomes too large

C No error, code runs correctly

D IndexOutOfRangeException due to incorrect power calculation

💡 Hint

Check how many times power is multiplied and what it represents.

The loop multiplies power prime times patternLength times, so power = prime^patternLength, but rolling hash needs prime^(patternLength-1). This causes logical error in hash update calculation.

🚀 Application

expert

Find all occurrences of pattern using Rabin Karp

Given the text "abracadabra" and pattern "abra", which indices will the Rabin Karp algorithm report as matches?

A [0, 7]

B [0, 3, 7]

C [1, 7]

D [0, 4, 7]

💡 Hint

Look for exact substring matches of "abra" in the text.

The pattern "abra" appears starting at index 0 and index 7 in "abracadabra". Other indices do not match the full pattern.

Practice

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

easy

A. Sort the text and pattern before matching

B. Compare each character of pattern with text directly

C. Use hashing to find pattern matches efficiently

D. Use recursion to find all pattern occurrences

Solution

1. Step 1: Understand Rabin Karp 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 of pattern with hash of text substrings to find matches efficiently.

3. Final Answer:

   Use hashing to find pattern matches efficiently -> Option C

4. Quick Check:

   Hashing = Efficient matching [OK]

Hint: Remember Rabin Karp uses hashing for fast pattern search [OK]

Common Mistakes:

• Thinking it compares characters one by one always
• Confusing with brute force matching
• Assuming sorting is involved

2. Which of the following is the correct way to calculate the initial hash for a substring in Rabin Karp (assuming base = 256 and prime = 101)?

easy

A. hash = (hash - char) % prime

B. hash = (hash + base * char) % prime

C. hash = (char * base) % prime

D. hash = (hash * base + char) % prime

Solution

1. Step 1: Understand rolling hash formula

   The rolling hash updates as hash = (hash * base + new_char) % prime.

2. Step 2: Apply formula for initial hash

   Initial hash is calculated by iterating characters and applying this formula cumulatively.

3. Final Answer:

   hash = (hash * base + char) % prime -> Option D

4. Quick Check:

   Rolling hash formula = hash = (hash * base + char) % prime [OK]

Hint: Use (hash * base + char) % prime for rolling hash [OK]

Common Mistakes:

• Adding instead of multiplying by base
• Subtracting characters incorrectly
• Ignoring modulo operation

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

string text = "ababc";
string pattern = "abc";
List<int> matches = RabinKarpSearch(text, pattern);
Console.WriteLine(string.Join(",", matches));

List<int> RabinKarpSearch(string txt, string pat) {
    int baseVal = 256, prime = 101;
    int m = pat.Length, n = txt.Length;
    int patHash = 0, txtHash = 0, h = 1;
    List<int> result = new List<int>();

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

    for (int i = 0; i < m; i++) {
        patHash = (baseVal * patHash + pat[i]) % prime;
        txtHash = (baseVal * txtHash + txt[i]) % prime;
    }

    for (int i = 0; i <= n - m; i++) {
        if (patHash == txtHash) {
            bool match = true;
            for (int j = 0; j < m; j++) {
                if (txt[i + j] != pat[j]) {
                    match = false;
                    break;
                }
            }
            if (match) result.Add(i);
        }
        if (i < n - m) {
            txtHash = (baseVal * (txtHash - txt[i] * h) + txt[i + m]) % prime;
            if (txtHash < 0) txtHash += prime;
        }
    }
    return result;
}

medium

A. 1,2

B. 2

C. 0,2

D. No matches

Solution

1. Step 1: Identify pattern occurrences in text

   Pattern "abc" appears starting at index 2 in "ababc". Also, substring at index 0 is "aba" which is not a match.

2. Step 2: Check hash and character matches

   Hashes match only at index 2 (initial hashes differ at index 0 and 1), and character check passes at index 2. So only index 2 is added.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Pattern found at index 2 [OK]

Hint: Check both hash and characters to confirm matches [OK]

Common Mistakes:

• Assuming all hash matches are valid
• Ignoring character verification after hash match
• Miscounting indices starting from 1

4. Identify the bug in this Rabin Karp substring search code snippet:

int baseVal = 256, prime = 101;
int m = pattern.Length, n = text.Length;
int patHash = 0, txtHash = 0, h = 1;
for (int i = 0; i <= m - 1; i++) h = (h * baseVal) % prime;
for (int i = 0; i < m; i++) {
    patHash = (baseVal * patHash + pattern[i]) % prime;
    txtHash = (baseVal * txtHash + text[i]) % prime;
}
// rest of code omitted

medium

A. Loop for h calculation should run till m-2, not m-1

B. Modulo prime missing in hash calculations

C. Using <= in loop causes out of range error

D. Base value should be 128, not 256

Solution

1. Step 1: Analyze h calculation loop

   h is used as base^(m-1) % prime, so loop should run m-1 times, i.e., i from 0 to m-2.

2. Step 2: Identify off-by-one error

   Loop runs from i=0 to i=m-1 (inclusive), which is m times, causing incorrect h value.

3. Final Answer:

   Loop for h calculation should run till m-2, not m-1 -> Option A

4. Quick Check:

   h loop runs m-1 times [OK]

Hint: Calculate h with loop running m-1 times only [OK]

Common Mistakes:

• Using <= instead of < in loop
• Forgetting modulo in hash updates
• Wrong base value choice

5. You want to find all occurrences of pattern "test" in a very large text using Rabin Karp. Which optimization helps reduce false positives caused by hash collisions?

hard

A. Use a larger prime number for modulo operations

B. Skip character comparison after hash match

C. Use base value as 1 to simplify hash

D. Only check first character after hash match

Solution

1. Step 1: Understand hash collisions in Rabin Karp

   Hash collisions occur when different substrings produce same hash value, causing false positives.

2. Step 2: Use larger prime to reduce collisions

   A larger prime number reduces chances of collisions by spreading hash values more evenly.

3. Final Answer:

   Use a larger prime number for modulo operations -> Option A

4. Quick Check:

   Larger prime = fewer collisions [OK]

Hint: Choose bigger prime to minimize hash collisions [OK]

Common Mistakes:

• Skipping character checks after hash match
• Using base 1 which weakens hash uniqueness
• Checking only first character after hash match