Rabin Karp String Matching in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Rabin Karp hash calculation

What is the output of the following Java code snippet that calculates the initial hash for the pattern "abc" using a base of 256 and a prime modulus 101?

DSA Java

int base = 256;
int prime = 101;
String pattern = "abc";
int hash = 0;
for (int i = 0; i < pattern.length(); i++) {
    hash = (hash * base + pattern.charAt(i)) % prime;
}
System.out.println(hash);

A 24

B 90

C 97

D 0

💡 Hint

Calculate hash step by step using modulo arithmetic.

The hash is calculated as (((0 * 256 + 'a') % 101) * 256 + 'b') % 101 * 256 + 'c') % 101. The final result is 90.

🧠 Conceptual

intermediate

Why use a prime modulus in Rabin Karp?

Why is a prime number used as the modulus in the Rabin Karp algorithm's hash function?

A Because prime numbers are easier to compute with in Java

B To make the hash function faster by using prime numbers

C To reduce the chance of hash collisions by spreading hash values uniformly

D To ensure the hash values are always positive

💡 Hint

Think about how hash collisions affect string matching accuracy.

Using a prime modulus helps distribute hash values more uniformly, reducing collisions and improving the algorithm's efficiency.

🔧 Debug

advanced

Identify the error in rolling hash update

What error will occur when running this Java code snippet that updates the rolling hash in Rabin Karp?

DSA Java

int base = 256;
int prime = 101;
int oldHash = 94;
int highBase = 256 * 256 % prime; // supposed to be base^(patternLength-1) mod prime
int oldChar = 'a';
int newChar = 'd';
int newHash = (oldHash - oldChar * highBase) * base + newChar % prime;
System.out.println(newHash);

A No error, the code runs and prints the correct new hash

B Runtime error due to integer overflow

C Syntax error due to missing semicolon

D The newHash calculation misses parentheses causing wrong modulo application

💡 Hint

Check operator precedence and modulo placement carefully.

The modulo operator applies only to newChar, not the entire expression, causing incorrect hash calculation.

🚀 Application

advanced

Find pattern occurrences using Rabin Karp

Given the text "abracadabra" and pattern "abra", which starting indices will the Rabin Karp algorithm find the pattern at?

A [0, 7]

B [0, 3, 7]

C [3, 7]

D [1, 7]

💡 Hint

Check all substrings of length equal to pattern and compare hashes.

The pattern "abra" appears at index 0 and index 7 in the text.

❓ Predict Output

expert

Output of Rabin Karp with collision check

What is the output of this Java code that uses Rabin Karp to find all occurrences of "test" in "this is a test text with test cases"?

DSA Java

import java.util.*;
public class RabinKarp {
    public static void main(String[] args) {
        String text = "this is a test text with test cases";
        String pattern = "test";
        int base = 256;
        int prime = 101;
        int m = pattern.length();
        int n = text.length();
        int patternHash = 0, textHash = 0, h = 1;
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < m - 1; i++) h = (h * base) % prime;
        for (int i = 0; i < m; i++) {
            patternHash = (base * patternHash + pattern.charAt(i)) % prime;
            textHash = (base * textHash + text.charAt(i)) % prime;
        }
        for (int i = 0; i <= n - m; i++) {
            if (patternHash == textHash) {
                int j;
                for (j = 0; j < m; j++) {
                    if (text.charAt(i + j) != pattern.charAt(j)) break;
                }
                if (j == m) result.add(i);
            }
            if (i < n - m) {
                textHash = (base * (textHash - text.charAt(i) * h) + text.charAt(i + m)) % prime;
                if (textHash < 0) textHash += prime;
            }
        }
        System.out.println(result);
    }
}

A [10, 25]

B [10]

C [25]

D []

💡 Hint

Check all occurrences of "test" in the text carefully.

The pattern "test" appears twice: starting at index 10 and index 25 in the text.

Practice

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

easy

A. It sorts the text and pattern before matching

B. It compares each character one by one without hashing

C. It uses hashing to find pattern matches efficiently

D. It uses recursion to find the pattern

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.

3. Final Answer:

   It uses 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 directly without hashing
• Confusing it with brute force matching
• Assuming it sorts strings before matching

2. Which of the following is the correct way to calculate the rolling hash in Rabin Karp for the next substring?

easy

A. new_hash = (old_hash - old_char * high_base) * base + new_char

B. new_hash = old_hash + old_char + new_char

C. new_hash = old_hash * old_char - new_char

D. new_hash = old_hash / base + new_char * high_base

Solution

1. Step 1: Recall rolling hash formula

   Rolling hash removes the old char's contribution and adds the new char's value.

2. Step 2: Apply formula correctly

   It subtracts old_char * high_base, multiplies by base, then adds new_char.

3. Final Answer:

   new_hash = (old_hash - old_char * high_base) * base + new_char -> Option A

4. Quick Check:

   Rolling hash formula = new_hash = (old_hash - old_char * high_base) * base + new_char [OK]

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

Common Mistakes:

• Adding old_char instead of subtracting
• Dividing instead of multiplying by base
• Ignoring the high_base multiplier

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

String text = "ababc";
String pattern = "abc";
List<Integer> result = rabinKarpSearch(text, pattern);
System.out.println(result);

Assume rabinKarpSearch returns a list of starting indices where pattern matches.

medium

A. []

B. [0, 2]

C. [1]

D. [2]

Solution

1. Step 1: Identify pattern occurrences in text

   Text: "ababc"; pattern: "abc"; check substrings of length 3: "aba"(0), "bab"(1), "abc"(2).

2. Step 2: Find matching indices

   Only substring starting at index 2 matches "abc".

3. Final Answer:

   [2] -> Option D

4. Quick Check:

   Pattern found at index 2 only [OK]

Hint: Check substrings of pattern length for exact matches [OK]

Common Mistakes:

• Including partial matches like "aba" or "bab"
• Assuming multiple matches without checking substring
• Confusing indices starting at 1 instead of 0

4. Consider this buggy Java snippet for Rabin Karp pattern search:

int base = 256;
int prime = 101;
int highBase = (int) Math.pow(base, pattern.length());
// ... rest of code
// rolling hash update:
currentHash = (currentHash - text.charAt(i) * highBase) * base + text.charAt(i + pattern.length());
currentHash %= prime;

What is the main bug here?

medium

A. highBase should be base^(pattern.length() - 1), not base^pattern.length()

B. Modulo operation should be before subtraction

C. Rolling hash should add old char, not subtract

D. Base should be 128, not 256

Solution

1. Step 1: Check highBase calculation

   High base is used to remove the leftmost character's contribution, so it should be base^(pattern length - 1).

2. Step 2: Identify incorrect power usage

   Using base^(pattern length) removes too much, causing wrong hash updates.

3. Final Answer:

   highBase should be base^(pattern.length() - 1), not base^pattern.length() -> Option A

4. Quick Check:

   Correct highBase power fixes rolling hash [OK]

Hint: Use base^(pattern length - 1) for highBase in rolling hash [OK]

Common Mistakes:

• Using base^pattern.length() instead of base^(pattern.length()-1)
• Ignoring modulo after subtraction
• Confusing addition and subtraction in rolling hash

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

hard

A. 2, because it skips overlapping matches

B. 4, because overlapping matches are counted

C. 3, because it counts only non-overlapping matches

D. 1, because it stops after first match

Solution

1. Step 1: Identify all substrings of length 3

   Text "aaaaaa" has substrings: "aaa"(0), "aaa"(1), "aaa"(2), "aaa"(3).

2. Step 2: Count overlapping matches

   All these substrings match pattern "aaa", so 4 matches found including overlaps.

3. Final Answer:

   4, because overlapping matches are counted -> Option B

4. Quick Check:

   Overlapping matches count = 4 [OK]

Hint: Rabin Karp counts overlapping matches by sliding one char at a time [OK]

Common Mistakes:

• Assuming matches cannot overlap
• Stopping search after first match
• Counting only non-overlapping matches