String Pattern Matching Naive in DSA Rust

Mental Model

Check every possible place in the text to see if the pattern matches exactly.

Analogy: Like looking for a small picture in a big photo by sliding it over every spot and checking if it fits perfectly.

Text:  H  E  L  L  O  W  O  R  L  D  
Index: 0  1  2  3  4  5  6  7  8  9
Pattern:     L  L  O
Positions to check: [0] [1] [2] [3] [4] [5] [6] [7]

Dry Run Walkthrough

Input: text: "HELLOWORLD", pattern: "LLO"

Goal: Find all starting positions in the text where the pattern "LLO" appears exactly.

Step 1: Check text starting at index 0 for pattern

Text: H E L L O W O R L D
Index:0 1 2 3 4 5 6 7 8 9
Pattern: L L O
Compare H vs L -> no match

Why: Start checking from the first character to see if pattern matches

Step 2: Check text starting at index 1 for pattern

Text: H E L L O W O R L D
Index:0 1 2 3 4 5 6 7 8 9
Pattern: L L O
Compare E vs L -> no match

Why: Move one step forward to check next possible start

Step 3: Check text starting at index 2 for pattern

Text: H E L L O W O R L D
Index:0 1 2 3 4 5 6 7 8 9
Pattern: L L O
Compare L vs L -> match
Compare L vs L -> match
Compare O vs O -> match
Pattern found at index 2

Why: All characters match, pattern found here

Step 4: Check text starting at index 3 for pattern

Text: H E L L O W O R L D
Index:0 1 2 3 4 5 6 7 8 9
Pattern: L L O
Compare L vs L -> match
Compare O vs L -> no match

Why: Mismatch found, move to next start

Step 5: Check text starting at index 4 for pattern

Text: H E L L O W O R L D
Index:0 1 2 3 4 5 6 7 8 9
Pattern: L L O
Compare O vs L -> no match

Why: Mismatch found, move to next start

Step 6: Check text starting at index 5 for pattern

Text: H E L L O W O R L D
Index:0 1 2 3 4 5 6 7 8 9
Pattern: L L O
Compare W vs L -> no match

Why: Mismatch found, move to next start

Result:

Pattern found at index 2

Annotated Code

DSA Rust

fn naive_pattern_match(text: &str, pattern: &str) -> Vec<usize> {
    let n = text.len();
    let m = pattern.len();
    let mut positions = Vec::new();
    if m == 0 || m > n {
        return positions; // pattern empty or longer than text
    }
    let text_bytes = text.as_bytes();
    let pattern_bytes = pattern.as_bytes();
    for i in 0..=n - m {
        let mut matched = true;
        for j in 0..m {
            if text_bytes[i + j] != pattern_bytes[j] {
                matched = false;
                break; // mismatch found, stop checking this position
            }
        }
        if matched {
            positions.push(i); // pattern found at index i
        }
    }
    positions
}

fn main() {
    let text = "HELLOWORLD";
    let pattern = "LLO";
    let matches = naive_pattern_match(text, pattern);
    if matches.is_empty() {
        println!("No match found");
    } else {
        for pos in matches {
            println!("Pattern found at index {}", pos);
        }
    }
}

for i in 0..=n - m {

slide pattern start index over text from 0 to last possible start

for j in 0..m {

check each character of pattern against text at current start

if text_bytes[i + j] != pattern_bytes[j] { matched = false; break; }

stop checking this start if any character mismatches

if matched { positions.push(i); }

record start index if full pattern matched

Output

Pattern found at index 2

Complexity Analysis

Time: O(n*m) because for each of the n-m+1 possible starts, we compare up to m characters

Space: O(k) where k is number of matches found, to store their start indices

vs Alternative: Naive is simple but slow; advanced algorithms like KMP reduce time to O(n) by avoiding repeated comparisons

Edge Cases

empty pattern

returns empty list immediately, no matches

DSA Rust

if m == 0 || m > n { return positions; }

pattern longer than text

returns empty list immediately, no matches

DSA Rust

if m == 0 || m > n { return positions; }

pattern not found in text

returns empty list, prints 'No match found'

DSA Rust

if matches.is_empty() { println!("No match found"); }

When to Use This Pattern

When you need to find if a small string appears inside a bigger string and no advanced algorithm is required, use naive pattern matching to check every possible position.

Common Mistakes

Mistake: Not stopping inner loop on first mismatch, causing unnecessary comparisons
Fix: Use break immediately when a mismatch is found inside the inner loop

Mistake: Not handling empty pattern or pattern longer than text, causing panic or wrong results
Fix: Add guard to return early if pattern length is zero or greater than text length

Summary

Checks every possible position in the text to find exact matches of the pattern.

Use when pattern matching needs are simple and input sizes are small.

The key insight is sliding the pattern over the text and stopping early on mismatches.

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