String Pattern Matching Naive in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the naive string pattern matching algorithm?

The naive algorithm checks for the pattern at every possible position in the text by comparing characters one by one until a match is found or all positions are checked.

beginner

In naive pattern matching, what happens when a mismatch occurs during comparison?

When a mismatch occurs, the algorithm shifts the pattern by one position to the right and starts comparing again from the beginning of the pattern.

intermediate

What is the worst-case time complexity of the naive string pattern matching algorithm?

The worst-case time complexity is O(m * n), where m is the length of the pattern and n is the length of the text, because it may check every character of the text for every character of the pattern.

beginner

Show a simple Rust code snippet for naive string pattern matching.

```rust
fn naive_search(text: &str, pattern: &str) -> Vec<usize> {
    let mut positions = Vec::new();
    let n = text.len();
    let m = pattern.len();
    if m > n {
        return vec![];
    }
    for i in 0..=n - m {
        if &text[i..i + m] == pattern {
            positions.push(i);
        }
    }
    positions
}
```

intermediate

Why is the naive pattern matching algorithm not efficient for large texts and patterns?

Because it checks every possible position and compares characters one by one without skipping, it can take a long time when the text and pattern are large or when many partial matches occur.

What does the naive string pattern matching algorithm do when it finds a mismatch?

A Shifts the pattern by one position and restarts comparison

B Stops searching immediately

C Skips multiple characters in the text

D Uses a preprocessed table to jump ahead

The naive algorithm shifts the pattern by one position to the right and starts comparing again from the beginning.

What is the worst-case time complexity of the naive pattern matching algorithm?

A O(n + m)

B O(m^2)

C O(m * n)

D O(n log m)

The worst-case time complexity is O(m * n), where m is pattern length and n is text length.

In the naive algorithm, how many positions in the text are checked for the pattern?

A Only the first position

B Positions based on a jump table

C Half of the positions

D All positions where the pattern fits

The algorithm checks all positions where the pattern can fit in the text.

Which of these is a key disadvantage of the naive pattern matching algorithm?

A Can be slow for large inputs due to repeated comparisons

B Requires extra memory for preprocessing

C Only works for numeric patterns

D Cannot find multiple occurrences

It can be slow because it compares characters repeatedly without skipping.

What does the naive pattern matching algorithm compare at each step?

A The entire text with the pattern at once

B Characters of the pattern with corresponding characters in the text one by one

C Only the first character of the pattern

D The pattern with a reversed text

It compares characters one by one between the pattern and the current text window.

Explain how the naive string pattern matching algorithm works step-by-step.

Think about sliding the pattern over the text and checking each position.

Describe the time complexity of the naive pattern matching algorithm and why it can be inefficient.

Consider how many comparisons happen in the worst case.

Practice

1. What is the main idea behind the naive string pattern matching algorithm?

easy

A. Check every possible position in the text for the pattern

B. Use a hash function to find the pattern quickly

C. Build a prefix table to skip unnecessary checks

D. Sort the text and pattern before matching

Solution

1. Step 1: Understand naive matching approach

   The naive algorithm tries to match the pattern starting at every position in the text.

2. Step 2: Compare with other methods

   Other methods like hashing or prefix tables are not part of naive matching.

3. Final Answer:

   Check every possible position in the text for the pattern -> Option A

4. Quick Check:

   Naive = Check all positions [OK]

Hint: Naive means try all positions one by one [OK]

Common Mistakes:

• Confusing naive with hashing or prefix methods
• Thinking naive skips positions
• Assuming sorting is involved

2. Which Rust code snippet correctly starts the naive pattern matching loop over text and pattern?

easy

A. for i in 0..text.len() + pattern.len() { /* check pattern */ }

B. for i in 0..=text.len() - pattern.len() { /* check pattern */ }

C. for i in 0..text.len() { /* check pattern */ }

D. for i in 0..pattern.len() { /* check pattern */ }

Solution

1. Step 1: Determine valid start positions

   The pattern can only start at positions where it fits fully in the text, so from 0 to text length minus pattern length.

2. Step 2: Check Rust range syntax

   Using 0..=text.len() - pattern.len() includes the last valid index.

3. Final Answer:

   for i in 0..=text.len() - pattern.len() { /* check pattern */ } -> Option B

4. Quick Check:

   Loop range = 0 to text.len()-pattern.len() [OK]

Hint: Loop till text length minus pattern length inclusive [OK]

Common Mistakes:

• Looping beyond valid start positions causing panic
• Using pattern length as loop limit
• Off-by-one errors in range

3. What will be the output of this Rust code using naive pattern matching?

let text = "abracadabra";
let pattern = "abra";
let mut positions = Vec::new();
for i in 0..=text.len() - pattern.len() {
    if &text[i..i+pattern.len()] == pattern {
        positions.push(i);
    }
}
println!("{:?}", positions);

medium

A. [3, 7]

B. [0, 3, 7]

C. [7]

D. [0, 7]

Solution

1. Step 1: Identify pattern matches in text

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

2. Step 2: Confirm positions collected

   Positions vector collects indices 0 and 7 where pattern matches exactly.

3. Final Answer:

   [0, 7] -> Option D

4. Quick Check:

   Matches at 0 and 7 only [OK]

Hint: Check substring slices equal to pattern [OK]

Common Mistakes:

• Including partial matches like at index 3
• Off-by-one errors in slicing
• Missing second occurrence

4. Identify the bug in this naive pattern matching Rust code:

let text = "hello";
let pattern = "ll";
for i in 0..text.len() - pattern.len() {
    if &text[i..i+pattern.len()] == pattern {
        println!("Found at {}", i);
    }
}

medium

A. Range should be 0..=text.len() - pattern.len() to include last position

B. Pattern length is used incorrectly in slicing

C. Text and pattern should be converted to chars before slicing

D. println! macro syntax is wrong

Solution

1. Step 1: Check loop range correctness

   The loop uses 0..text.len() - pattern.len(), which excludes the last valid start index.

2. Step 2: Fix range to include last index

   Using 0..=text.len() - pattern.len() includes the last position where pattern can start.

3. Final Answer:

   Range should be 0..=text.len() - pattern.len() to include last position -> Option A

4. Quick Check:

   Use inclusive range for last valid index [OK]

Hint: Use inclusive range to cover all valid start indices [OK]

Common Mistakes:

• Using exclusive range causing missed matches
• Incorrect slicing indices
• Unnecessary conversion to chars

5. Given a text and a pattern, how can you modify the naive pattern matching to count overlapping occurrences of the pattern in Rust?
Example: text = "aaaa", pattern = "aa" should count 3 occurrences.

hard

A. Increment index by pattern length after each match

B. Use a hash map to store counts

C. Increment index by 1 after each check instead of pattern length

D. Reverse the text and pattern before matching

Solution

1. Step 1: Understand overlapping matches

   Overlapping means after finding a match, next check starts just one position ahead, not skipping full pattern length.

2. Step 2: Adjust loop increment

   Increment index by 1 each time to allow overlapping matches to be found.

3. Final Answer:

   Increment index by 1 after each check instead of pattern length -> Option C

4. Quick Check:

   Step by 1 to count overlaps [OK]

Hint: Move index by 1 to catch overlaps [OK]

Common Mistakes:

• Skipping by pattern length missing overlaps
• Using hash map unnecessarily
• Reversing strings does not help