Rabin Karp String Matching in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the Rabin Karp string matching algorithm?

It uses hashing to find a pattern in a text by comparing hash values of the pattern and substrings of the text, reducing the number of direct character comparisons.

intermediate

Why does Rabin Karp use a rolling hash?

A rolling hash allows efficient calculation of the hash for the next substring by updating the previous hash, avoiding recomputing from scratch.

intermediate

What happens if two substrings have the same hash value in Rabin Karp?

Since hash collisions can occur, the algorithm checks the actual characters of the substrings to confirm if they really match.

intermediate

In Rabin Karp, what is the typical time complexity for searching a pattern in a text?

Average case is O(n + m), where n is text length and m is pattern length; worst case can be O(n*m) due to hash collisions.

intermediate

What role does the modulus play in Rabin Karp's hashing?

The modulus keeps hash values within a fixed range to avoid overflow and helps in distributing hash values uniformly.

What does Rabin Karp primarily use to speed up pattern matching?

A Hashing of substrings

B Sorting the text

C Binary search

D Dynamic programming

Rabin Karp uses hashing of substrings to quickly compare pattern and text parts.

What is a rolling hash in Rabin Karp?

A A hash that is recalculated from scratch each time

B A hash that ignores collisions

C A hash that only works for fixed-length strings

D A hash that updates efficiently when moving to the next substring

Rolling hash updates the hash value efficiently when sliding over the text.

If two substrings have the same hash in Rabin Karp, what is the next step?

A Assume they match and return true

B Check the actual characters to confirm

C Ignore the match and continue

D Restart the algorithm

Due to possible collisions, actual characters are checked to confirm a match.

What is the worst-case time complexity of Rabin Karp?

A O(log n)

B O(n + m)

C O(n * m)

D O(m^2)

Worst case is O(n * m) due to many hash collisions requiring character checks.

Why is modulus used in Rabin Karp hashing?

A To keep hash values within a fixed range and avoid overflow

B To speed up string comparisons

C To sort the hash values

D To encrypt the pattern

Modulus keeps hash values manageable and helps distribute them evenly.

Explain how the Rabin Karp algorithm uses hashing to find a pattern in a text.

Think about how hash values help avoid checking every character.

Describe the role of the rolling hash and modulus in Rabin Karp string matching.

Focus on how the hash value changes as the window moves.

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