Substring Search Patterns in DSA Rust - Execution Trace

Concept Flow - Substring Search Patterns

Start at index 0 in text

↓

Compare substring with text segment

↓

Match?

No→Move to next index

↓

Reached end of text?

↓

Return match index

↓

Done

Start from the beginning of the text, compare the substring at each position, move forward if no match, stop when match found or text ends.

Execution Sample

DSA Rust

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

This code searches for the substring "lo" in "hello world" by checking each possible position.

Execution Table

Step	Operation	Index i	Text Segment Compared	Match?	Action	Visual State
1	Compare substring with text segment	0	"he"	No	Move to next index	Text: h e l l o w o r l d Index: 0 1 2 3 4 5 6 7 8 9 10
2	Compare substring with text segment	1	"el"	No	Move to next index	Text: h e l l o w o r l d Index: 0 1 2 3 4 5 6 7 8 9 10
3	Compare substring with text segment	2	"ll"	No	Move to next index	Text: h e l l o w o r l d Index: 0 1 2 3 4 5 6 7 8 9 10
4	Compare substring with text segment	3	"lo"	Yes	Return match index 3	Text: h e l l o w o r l d Index: 0 1 2 3 4 5 6 7 8 9 10
5	Stop	-	-	-	Match found, stop searching	Text: h e l l o w o r l d Index: 0 1 2 3 4 5 6 7 8 9 10

💡 Match found at index 3, search stops.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
i	0	1	2	3	3	3
Text Segment Compared	"he"	"el"	"ll"	"lo"	"lo"	"lo"
Match?	No	No	No	Yes	Yes	Yes

Key Moments - 3 Insights

Why do we stop checking after index 3 in this example?

Because the substring length is 2, and the last possible start index is text length - substring length = 11 - 2 = 9. But since we found a match at index 3 (see execution_table step 4), we stop searching early.

Why do we compare text segments of length equal to the substring?

To check if the substring matches exactly at that position, we compare a segment of the text with the same length as the substring (see execution_table column 'Text Segment Compared').

What happens if the substring is not found in the text?

The loop continues until the last possible index, and if no match is found, the search ends without returning an index (not shown in this example but implied by exit conditions).

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'i' when the substring matches?

A 3

B 2

C 4

D 0

💡 Hint

Check the 'Index i' column at the step where 'Match?' is 'Yes' (step 4).

At which step does the search stop according to the execution_table?

A Step 3

B Step 5

C Step 4

D Step 2

💡 Hint

Look for the step with action 'Match found, stop searching' in the 'Action' column.

If the substring was "wo" instead of "lo", at which index would the match occur?

A 6

B 3

C 4

D 7

💡 Hint

Visualize the text and find where "wo" appears; check the 'Index i' positions in the variable_tracker.

Concept Snapshot

Substring Search Patterns:
- Start from index 0 in text
- Compare substring length segment at each index
- If match, return index
- Else, move to next index
- Stop when match found or end reached

Full Transcript

This visualization shows how substring search works by checking each possible position in the text for a match with the substring. We start at index 0 and compare the substring length segment of the text. If it matches, we return the index and stop. If not, we move to the next index and repeat until we find a match or reach the end of the text. The example searches for "lo" in "hello world" and finds it at index 3.

Practice

1. What is the main purpose of substring search algorithms in strings?

easy

A. To find if a smaller string exists inside a larger string

B. To sort characters in a string alphabetically

C. To reverse the order of characters in a string

D. To count the total number of characters in a string

Solution

1. Step 1: Understand substring search goal

   Substring search algorithms check if a smaller string (pattern) appears inside a bigger string (text).

2. Step 2: Compare with other string operations

   Sorting, reversing, and counting characters are different operations unrelated to searching for a substring.

3. Final Answer:

   To find if a smaller string exists inside a larger string -> Option A

4. Quick Check:

   Substring search = find smaller string inside bigger string [OK]

Hint: Substring search means finding a smaller string inside a bigger one [OK]

Common Mistakes:

• Confusing substring search with sorting or reversing strings
• Thinking substring search counts characters
• Mixing substring search with string length calculation

2. Which Rust code snippet correctly checks if the string needle is a substring of haystack?

easy

A. if haystack.index_of(needle) { println!("Found"); }

B. if haystack.find(needle) { println!("Found"); }

C. if needle.in(haystack) { println!("Found"); }

D. if haystack.contains(needle) { println!("Found"); }

Solution

1. Step 1: Identify correct Rust substring method

   Rust's standard library provides contains method on strings to check substring presence, returning a boolean.

2. Step 2: Check other options for syntax errors

   find returns an Option, not a boolean; in is not a Rust keyword; index_of does not exist in Rust standard strings.

3. Final Answer:

   if haystack.contains(needle) { println!("Found"); } -> Option D

4. Quick Check:

   Rust substring check uses contains() [OK]

Hint: Use .contains() to check substring presence in Rust strings [OK]

Common Mistakes:

• Using .find() as a boolean without checking Option
• Trying Python or other language syntax like 'in'
• Using non-existent methods like index_of

3. What will be the output of this Rust code?

let text = "hello world";
let pattern = "wor";
if text.contains(pattern) {
    println!("Pattern found");
} else {
    println!("Pattern not found");
}

medium

A. Compilation error

B. Pattern found

C. Pattern not found

D. Runtime panic

Solution

1. Step 1: Check if pattern is substring of text

   The string "hello world" contains "wor" starting at index 6.

2. Step 2: Evaluate the if condition

   Since text.contains(pattern) returns true, the code prints "Pattern found".

3. Final Answer:

   Pattern found -> Option B

4. Quick Check:

   "hello world" contains "wor" = true [OK]

Hint: Check if substring exists literally inside the main string [OK]

Common Mistakes:

• Assuming contains() checks for whole words only
• Confusing contains() with starts_with() or ends_with()
• Expecting compilation or runtime errors without syntax issues

4. Identify the error in this Rust code snippet for substring search:

let text = "rustacean";
let pattern = "ace";
if text.find(pattern) {
    println!("Found");
} else {
    println!("Not found");
}

medium

A. Missing semicolon after let statements

B. Using contains() instead of find()

C. Using find() without handling Option result

D. Pattern string is empty

Solution

1. Step 1: Understand return type of find()

   In Rust, find() returns an Option<usize>, not a boolean.

2. Step 2: Check if condition usage

   The if condition expects a boolean, but text.find(pattern) returns Option, causing a type mismatch error.

3. Final Answer:

   Using find() without handling Option result -> Option C

4. Quick Check:

   find() returns Option, not bool [OK]

Hint: Remember find() returns Option, not boolean; unwrap or check Some [OK]

Common Mistakes:

• Treating find() as boolean directly in if
• Ignoring Option type returned by find()
• Confusing contains() and find() return types

5. Given a large text and multiple patterns, which substring search approach is best to efficiently find all patterns in the text?

hard

A. Using a Trie or Aho-Corasick algorithm to search all patterns simultaneously

B. Naive search checking each pattern separately in the text

C. Sorting all patterns and text then binary searching each pattern

D. Reversing the text and patterns before searching

Solution

1. Step 1: Analyze naive approach inefficiency

   Checking each pattern separately in a large text is slow because it repeats scanning multiple times.

2. Step 2: Understand advanced multi-pattern search

   Trie-based algorithms like Aho-Corasick build a structure to search all patterns at once efficiently.

3. Step 3: Evaluate other options

   Sorting and binary searching patterns is not suitable for substring search; reversing strings does not help search efficiency.

4. Final Answer:

   Using a Trie or Aho-Corasick algorithm to search all patterns simultaneously -> Option A

5. Quick Check:

   Multi-pattern search uses Trie/Aho-Corasick [OK]

Hint: Use Trie or Aho-Corasick for multiple substring searches efficiently [OK]

Common Mistakes:

• Using naive repeated searches for many patterns
• Trying sorting-based methods for substring search
• Thinking reversing strings improves search speed