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 patternHash = 0;
for (int i = 0; i < pattern.Length; i++) {
    patternHash = (patternHash * baseVal + pattern[i]) % [1];
}

Drag options to blanks, or click blank then click option'

Aprime

Bpattern.Length

Ctext.Length

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 as modulo causes division by zero error.

Using pattern.Length or text.Length as modulo leads to poor hashing.

The hash value is computed modulo a prime number to reduce collisions.

2fill in blank

medium

Complete the code to update the rolling hash when sliding the window over the text.

DSA C#

textHash = (textHash - text[i] * highBase) * baseVal + text[i + pattern.Length];
textHash = (textHash + [1]) % prime;

Drag options to blanks, or click blank then click option'

Atext.Length

Bpattern.Length

Cprime

Dprime * prime

Attempts:

3 left

💡 Hint

Common Mistakes

Not adding prime before modulo causes negative hash values.

Using incorrect values instead of prime leads to wrong hash updates.

Adding prime before modulo ensures the hash value stays positive.

3fill in blank

hard

Fix the error in the hash comparison condition to avoid false positives.

DSA C#

if (patternHash == textHash && text.Substring(i, pattern.Length) == [1]) {
    result.Add(i);
}

Drag options to blanks, or click blank then click option'

Atext

BpatternHash

CtextHash

Dpattern

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing substring with text or hash values causes logic errors.

Skipping substring comparison leads to false matches.

After hash match, confirm by comparing the actual substring with the pattern.

4fill in blank

hard

Fill both blanks to compute the highest base power used in rolling hash.

DSA C#

int highBase = 1;
for (int i = 0; i < [1] - 1; i++) {
    highBase = (highBase * [2]) % prime;
}

Drag options to blanks, or click blank then click option'

Apattern.Length

Btext.Length

CbaseVal

Dprime

Attempts:

3 left

💡 Hint

Common Mistakes

Using text.Length instead of pattern.Length causes wrong power calculation.

Using prime instead of baseVal in multiplication is incorrect.

The highest base power is baseVal^(pattern.Length-1) modulo prime.

5fill in blank

hard

Fill all three blanks to complete the Rabin-Karp search loop.

DSA C#

for (int i = 0; i <= text.Length - [1]; i++) {
    if (patternHash == textHash) {
        if (text.Substring(i, [2]) == [3]) {
            result.Add(i);
        }
    }
    if (i < text.Length - [1]) {
        textHash = (textHash - text[i] * highBase) * baseVal + text[i + [1]];
        textHash = (textHash + prime) % prime;
    }
}

Drag options to blanks, or click blank then click option'

Apattern.Length

Bpattern

Dtext.Length

Attempts:

3 left

💡 Hint

Common Mistakes

Using text.Length instead of pattern.Length causes index errors.

Comparing substring with text instead of pattern causes false matches.

Use pattern.Length for substring length and loop limit, and compare substring with 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