Rabin Karp String Matching in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to calculate the initial hash of the pattern.

DSA Rust

let mut pattern_hash = 0u64;
for &byte in pattern.as_bytes() {
    pattern_hash = (pattern_hash * base + [1] as u64) % modulus;
}

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

Abyte

Bpattern

Cmodulus

Dbase

Attempts:

3 left

💡 Hint

Common Mistakes

Using the whole pattern string instead of the current byte.

Using modulus or base instead of the byte value.

The hash is calculated by adding the byte value of each character in the pattern.

2fill in blank

medium

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

DSA Rust

text_hash = (text_hash + modulus - (old_char as u64 * high_base) % modulus) % modulus;
text_hash = (text_hash * base + [1] as u64) % modulus;

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

Aold_char

Bbase

Cnew_char

Dmodulus

Attempts:

3 left

💡 Hint

Common Mistakes

Using old_char instead of new_char.

Using base or modulus instead of character byte.

When sliding the window, add the new character's byte to the rolling hash.

3fill in blank

hard

Fix the error in the hash comparison condition to check for a match.

DSA Rust

if text_hash == [1] && &text[i..i+pattern_len] == pattern {
    result.push(i);
}

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

Abase

Btext_hash

Cmodulus

Dpattern_hash

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing text_hash to itself.

Comparing to modulus or base instead of pattern_hash.

The rolling hash of the current text window should be compared to the pattern's hash.

4fill in blank

hard

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

DSA Rust

let mut high_base = 1u64;
for _ in 1..[1] {
    high_base = (high_base * [2]) % modulus;
}

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

Apattern_len

Btext_len

Cbase

Dmodulus

Attempts:

3 left

💡 Hint

Common Mistakes

Using text_len instead of pattern_len.

Using modulus instead of base in multiplication.

high_base is base raised to the power of pattern length minus one, modulo modulus.

5fill in blank

hard

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

DSA Rust

fn rabin_karp_search(text: &str, pattern: &str) -> Vec<usize> {
    let base = 256u64;
    let modulus = 101u64;
    let pattern_len = pattern.len();
    let text_len = text.len();
    if pattern_len > text_len {
        return vec![];
    }
    let mut pattern_hash = 0u64;
    let mut text_hash = 0u64;
    let mut high_base = 1u64;
    for _ in 1..pattern_len {
        high_base = (high_base * [1]) % modulus;
    }
    for i in 0..pattern_len {
        pattern_hash = (pattern_hash * [2] + pattern.as_bytes()[i] as u64) % modulus;
        text_hash = (text_hash * [2] + text.as_bytes()[i] as u64) % modulus;
    }
    let mut result = Vec::new();
    for i in 0..=text_len - pattern_len {
        if text_hash == pattern_hash && &text[i..i+pattern_len] == pattern {
            result.push(i);
        }
        if i < text_len - pattern_len {
            text_hash = (text_hash + modulus - (text.as_bytes()[i] as u64 * high_base) % modulus) % modulus;
            text_hash = (text_hash * [3] + text.as_bytes()[i + pattern_len] as u64) % modulus;
        }
    }
    result
}

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

Abase

Bmodulus

Dpattern_len

Attempts:

3 left

💡 Hint

Common Mistakes

Using modulus instead of base for multiplication.

Mixing up base and modulus in hash calculations.

The base is used for power calculation and hash updates. modulus is used only for modulo operations.

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