String Pattern Matching Naive in DSA Rust - Execution Trace

Concept Flow - String Pattern Matching Naive

Start at text index i=0

↓

Compare pattern with text at i

↓

Match all pattern chars?

Yes→Record match at i

No↓

Increment i by 1

↓

Check if i <= text_len - pattern_len

Yes↓

Repeat

No↓

End

The algorithm tries to match the pattern starting at each position in the text one by one until it reaches the end.

Execution Sample

DSA Rust

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

This code checks every possible position in the text to see if the pattern matches starting there.

Execution Table

Step	Operation	Text Index i	Pattern Matched?	Match Positions Found	Visual State
1	Compare text[0..3] with pattern	0	Yes	[0]	"ABA"BABA
2	Compare text[1..4] with pattern	1	No	[0]	A"BAB"ABA
3	Compare text[2..5] with pattern	2	Yes	[0, 2]	AB"ABA"BA
4	Compare text[3..6] with pattern	3	No	[0, 2]	ABA"BAB"A
5	Compare text[4..7] with pattern	4	Yes	[0, 2, 4]	ABAB"ABA"
6	Check i=5 > 7-3=4, stop	5	N/A	[0, 2, 4]	ABABA"BA" (stop)

💡 i reached 5 which is beyond text length minus pattern length, so matching stops.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
i	0	0	1	2	3	4	5
Match Positions	[]	[0]	[0]	[0, 2]	[0, 2]	[0, 2, 4]	[0, 2, 4]

Key Moments - 3 Insights

Why do we stop checking when i > text length - pattern length?

Because starting beyond that point, the pattern would not fit fully inside the text. See execution_table row 6 where i=5 stops the loop.

Why do some comparisons result in 'No' even though some characters match?

The algorithm requires the entire pattern to match exactly. Partial matches are not enough. See execution_table rows 2 and 4 where partial matches fail.

How does the algorithm find multiple matches overlapping in the text?

It checks every position independently, so overlapping matches are found separately. See matches at positions 0, 2, and 4 in execution_table rows 1, 3, and 5.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of i when the second match is found?

A 1

B 2

C 3

D 4

💡 Hint

Check the 'Text Index i' and 'Pattern Matched?' columns in execution_table rows.

At which step does the algorithm stop checking further positions?

A Step 4

B Step 5

C Step 6

D Step 7

💡 Hint

Look at the 'Operation' column and the exit_note in execution_table.

If the pattern was "BAB" instead of "ABA", which positions would be matched?

A [1, 3]

B [0, 2, 4]

C [2, 4]

D [1, 4]

💡 Hint

Think about where "BAB" appears in the text "ABABABA" and relate to variable_tracker.

Concept Snapshot

Naive String Pattern Matching:
- Check pattern at every text index from 0 to text_len - pattern_len
- Compare substring with pattern fully
- Record index if full match
- Stop when pattern can't fit
- Simple but inefficient for large texts

Full Transcript

The naive string pattern matching algorithm tries to find all occurrences of a pattern inside a text by checking every possible starting position. It compares the pattern characters one by one with the text substring at that position. If all characters match, it records the position. The process repeats by moving one position forward until the pattern no longer fits inside the remaining text. This method is straightforward but can be slow for large inputs because it checks every position without skipping.

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