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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Rabin Karp hash calculation

What is the output of the following Rust code that calculates the initial hash for the pattern and the first window of the text using Rabin Karp algorithm?

DSA Rust

fn main() {
    let text = "abcde";
    let pattern = "abc";
    let base: u64 = 256;
    let prime: u64 = 101;
    let m = pattern.len();
    let mut pattern_hash = 0u64;
    let mut text_hash = 0u64;
    let mut h = 1u64;

    for _ in 0..m-1 {
        h = (h * base) % prime;
    }

    for i in 0..m {
        pattern_hash = (base * pattern_hash + pattern.as_bytes()[i] as u64) % prime;
        text_hash = (base * text_hash + text.as_bytes()[i] as u64) % prime;
    }

    println!("pattern_hash: {}", pattern_hash);
    println!("text_hash: {}", text_hash);
}

A

pattern_hash: 24
text_hash: 24

B

pattern_hash: 97
text_hash: 97

C

pattern_hash: 6
text_hash: 6

D

pattern_hash: 15
text_hash: 15

💡 Hint

Remember to apply modulo operation after each multiplication and addition.

The code calculates the hash of the pattern "abc" and the first window "abc" in the text using base 256 and prime 101. The resulting hash values are both 6.

🧠 Conceptual

intermediate

Understanding the rolling hash update in Rabin Karp

In Rabin Karp algorithm, when sliding the window by one character, how is the new hash value computed from the old hash value?

A Remove the leftmost character's contribution, multiply the remaining hash by base, add the new rightmost character, then take modulo prime.

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

C Recalculate the hash from scratch for the new window without using the old hash.

D Multiply the old hash by the prime number and add the new character's ASCII value.

💡 Hint

Think about how to efficiently update the hash without full recomputation.

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

🔧 Debug

advanced

Identify the error in this Rabin Karp hash update code

What error will this Rust code produce when updating the rolling hash in Rabin Karp algorithm?

DSA Rust

fn update_hash(old_hash: u64, left_char: u8, new_char: u8, h: u64, base: u64, prime: u64) -> u64 {
    let mut new_hash = base * (old_hash - (left_char as u64) * h) + (new_char as u64);
    new_hash %= prime;
    new_hash
}

fn main() {
    let old_hash = 6;
    let left_char = b'a';
    let new_char = b'd';
    let h = 65536;
    let base = 256;
    let prime = 101;
    let updated_hash = update_hash(old_hash, left_char, new_char, h, base, prime);
    println!("Updated hash: {}", updated_hash);
}

A The code will panic due to integer overflow in multiplication.

B The code will produce a negative hash value causing runtime error.

C The code will compile and run correctly, printing the updated hash.

D The code will cause a division by zero error.

💡 Hint

Check the multiplication of large numbers and the type used.

Multiplying large u64 values without checked arithmetic can overflow silently in Rust, but in debug mode it panics. The value h=65536 is large and multiplied by base and old_hash can overflow u64.

🚀 Application

advanced

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 [3, 7]

B [0, 3, 7]

C [1, 7]

D [0, 7]

💡 Hint

Check where the pattern "abra" appears exactly in the text.

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

🧠 Conceptual

expert

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

What is the main reason for using a prime number as the modulus in the Rabin Karp rolling hash function?

A To simplify the subtraction operation in rolling hash updates.

B To reduce the number of hash collisions by distributing hash values uniformly.

C To ensure the hash values are always positive integers.

D To make the hash calculation faster by using prime arithmetic.

💡 Hint

Think about how modulus affects hash distribution.

Using a prime modulus helps spread hash values more uniformly, reducing collisions and improving algorithm efficiency.

Practice

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

easy

A. It uses hashing to find pattern matches efficiently in a text.

B. It compares each character of the pattern with the text directly.

C. It sorts the text and pattern before matching.

D. It uses recursion to find all pattern matches.

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 in a text. -> Option A

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 it with sorting-based algorithms
• Assuming it uses recursion

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

easy

A. hash = (hash - old_char * power) * base + new_char;

B. hash = hash + old_char - new_char * base;

C. hash = (hash + old_char) * base - new_char;

D. hash = (hash * base) - old_char + new_char * power;

Solution

1. Step 1: Recall rolling hash formula

   To move the window, subtract old char's weighted value, multiply by base, add new char.

2. Step 2: Match formula with options

   hash = (hash - old_char * power) * base + new_char; matches the formula: hash = (hash - old_char * power) * base + new_char;

3. Final Answer:

   hash = (hash - old_char * power) * base + new_char; -> Option A

4. Quick Check:

   Rolling hash update = hash = (hash - old_char * power) * base + new_char; [OK]

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

Common Mistakes:

• Adding old char instead of subtracting
• Wrong order of operations
• Multiplying new char incorrectly

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

let text = "ababc";
let pattern = "abc";
let result = rabin_karp_search(text, pattern);
println!("{:?}", result);

Assume rabin_karp_search returns a vector of starting indices where pattern matches.

medium

A. [0, 2]

B. [1, 3]

C. [2]

D. []

Solution

1. Step 1: Identify pattern occurrences in text

   Text: "ababc"; pattern: "abc"; pattern appears starting at index 2 only.

2. Step 2: Confirm output of search function

   The function returns indices where pattern matches, so output is [2].

3. Final Answer:

   [2] -> Option C

4. Quick Check:

   Pattern at index 2 only [OK]

Hint: Check substring positions carefully [OK]

Common Mistakes:

• Counting overlapping matches incorrectly
• Starting index off by one
• Assuming multiple matches where only one exists

4. Consider this Rust code snippet for Rabin Karp. It does not find any matches even though the pattern exists. What is the bug?

fn rabin_karp_search(text: &str, pattern: &str) -> Vec<usize> {
    let base = 256;
    let prime = 101;
    let m = pattern.len();
    let n = text.len();
    let mut pattern_hash = 0;
    let mut text_hash = 0;
    let mut power = 1;

    for _ in 0..m-1 {
        power = (power * base) % prime;
    }

    for i in 0..m {
        pattern_hash = (base * pattern_hash + pattern.as_bytes()[i] as usize) % prime;
        text_hash = (base * text_hash + text.as_bytes()[i] as usize) % prime;
    }

    let mut result = Vec::new();
    for i in 0..=n-m {
        if pattern_hash == text_hash {
            if &text[i..i+m] == pattern {
                result.push(i);
            }
        }
        if i < n - m {
            text_hash = (base * (text_hash - (text.as_bytes()[i] as usize) * power) + text.as_bytes()[i + m] as usize) % prime;
            if text_hash < 0 {
                text_hash += prime;
            }
        }
    }
    result
}

medium

A. The pattern and text hashes are calculated incorrectly using bytes.

B. The power calculation loop should run from 0 to m, not m-1.

C. The loop should run from 0 to n-m-1, not 0 to n-m.

D. The modulo operation can produce negative values; need to add prime after subtraction.

Solution

1. Step 1: Analyze rolling hash update

   Subtracting (text[i] * power) can cause negative value before modulo.

2. Step 2: Fix negative modulo issue

   Adding prime after subtraction ensures positive modulo result.

3. Final Answer:

   The modulo operation can produce negative values; need to add prime after subtraction. -> Option D

4. Quick Check:

   Modulo negative fix = The modulo operation can produce negative values; need to add prime after subtraction. [OK]

Hint: Add prime after subtraction to avoid negative modulo [OK]

Common Mistakes:

• Ignoring negative modulo results
• Wrong loop ranges for power calculation
• Misusing byte conversions

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. 3 matches, because only non-overlapping occurrences are counted.

B. 4 matches, because overlapping occurrences are counted.

C. 1 match, because repeated characters cause hash collisions.

D. 0 matches, because the algorithm fails on repeated characters.

Solution

1. Step 1: Identify overlapping pattern occurrences

   Text "aaaaaa" contains "aaa" starting at indices 0,1,2,3 (4 matches).

2. Step 2: Rabin Karp counts overlapping matches

   Algorithm checks every substring of length pattern, so all 4 matches are found.

3. Final Answer:

   4 matches, because overlapping occurrences are counted. -> Option B

4. Quick Check:

   Overlapping matches counted = 4 [OK]

Hint: Rabin Karp finds overlapping matches too [OK]

Common Mistakes:

• Assuming only non-overlapping matches count
• Thinking hash collisions prevent matches
• Believing repeated chars cause failure