Rabin Karp String Matching in DSA Rust - Build from Scratch

Rabin Karp String Matching

📖 Scenario: Imagine you are building a simple search tool that finds a small word inside a big text. This is like looking for a friend's name in a long letter. We will use a smart way called Rabin Karp to find the word quickly.

🎯 Goal: Build a program that uses the Rabin Karp method to find all places where a small word (pattern) appears inside a bigger text. You will create the text and pattern, set up the hashing system, write the matching logic, and finally print the positions where the pattern is found.

📋 What You'll Learn

Create a string variable called text with the value "abracadabra"

Create a string variable called pattern with the value "abra"

Create integer variables prime with value 101 and base with value 256

Write the Rabin Karp algorithm to find all starting indices where pattern appears in text

Print the list of starting indices as a vector

💡 Why This Matters

🌍 Real World

Rabin Karp is used in text editors, search engines, and plagiarism detection tools to quickly find patterns in large texts.

💼 Career

Understanding Rabin Karp helps in roles involving text processing, software development, and algorithm optimization.

1

Create the text and pattern strings

Create a string variable called text with the value "abracadabra" and a string variable called pattern with the value "abra".

DSA Rust

# Create the text and pattern strings
# Your code here

Hint

Use let to create variables for text and pattern with the exact strings.

2

Set up the hashing base and prime number

Add integer variables called prime with value 101 and base with value 256 inside the main function after the text and pattern declarations.

DSA Rust

fn main() {
    let text = "abracadabra";
    let pattern = "abra";
    // Add prime and base variables here
    # Your code here
}

Hint

Use let to create prime and base with the exact values.

3

Implement the Rabin Karp matching logic

Write the Rabin Karp algorithm inside the main function to find all starting indices where pattern appears in text. Use variables prime and base for hashing. Store the matching indices in a vector called result.

DSA Rust

fn main() {
    let text = "abracadabra";
    let pattern = "abra";
    let prime = 101;
    let base = 256;
    // Implement Rabin Karp algorithm here
    # Your code here
}

Hint

Calculate initial hashes, then slide over text to compare hashes and check actual substring. Store matches in result.

4

Print the matching indices

Add a print statement to display the vector result which contains all starting indices where pattern is found in text.

DSA Rust

fn main() {
    let text = "abracadabra";
    let pattern = "abra";
    let prime = 101;
    let base = 256;

    let n = text.len();
    let m = pattern.len();
    let text_bytes = text.as_bytes();
    let pattern_bytes = pattern.as_bytes();

    let mut pattern_hash = 0;
    let mut text_hash = 0;
    let mut h = 1;

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

    for i in 0..m {
        pattern_hash = (base * pattern_hash + pattern_bytes[i] as i32) % prime;
        text_hash = (base * text_hash + text_bytes[i] as i32) % 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_bytes[i] as i32) * h) + text_bytes[i + m] as i32) % prime;
            if text_hash < 0 {
                text_hash += prime;
            }
        }
    }
    // Print the result vector
    # Your code here
}

Hint

Use println!("{:?}", result); to print the vector of indices.

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