Substring Search Patterns in DSA Rust

Mental Model

Find if a smaller word appears inside a bigger word by checking each possible starting point.

Analogy: Like looking for a small sticker hidden somewhere on a long ribbon by sliding your eyes along the ribbon piece by piece.

Big word: H -> E -> L -> L -> O -> null
Small word: L -> L -> null

We try to match small word starting at each letter of big word.

Dry Run Walkthrough

Input: big word: HELLO, small word: LL

Goal: Find if 'LL' appears inside 'HELLO' and where it starts

Step 1: Check if 'LL' matches starting at 'H'

H[0] E[1] L[2] L[3] O[4]
Trying to match 'LL' at index 0: H vs L -> no match

Why: We start checking from the first letter of big word

Step 2: Check if 'LL' matches starting at 'E'

H[0] E[1] L[2] L[3] O[4]
Trying to match 'LL' at index 1: E vs L -> no match

Why: Move one letter forward to try next possible start

Step 3: Check if 'LL' matches starting at first 'L'

H[0] E[1] L[2] L[3] O[4]
Trying to match 'LL' at index 2: L vs L -> match
Next letter: L vs L -> match

Why: Found matching letters for whole small word

Result:

H[0] E[1] L[2] L[3] O[4]
Match found starting at index 2

Annotated Code

DSA Rust

fn substring_search(big: &str, small: &str) -> Option<usize> {
    let big_chars: Vec<char> = big.chars().collect();
    let small_chars: Vec<char> = small.chars().collect();
    if small_chars.is_empty() {
        return Some(0); // empty string matches at start
    }
    for i in 0..=big_chars.len().saturating_sub(small_chars.len()) {
        let mut matched = true;
        for j in 0..small_chars.len() {
            if big_chars[i + j] != small_chars[j] {
                matched = false;
                break; // mismatch found, stop checking this start
            }
        }
        if matched {
            return Some(i); // found match starting at i
        }
    }
    None // no match found
}

fn main() {
    let big = "HELLO";
    let small = "LL";
    match substring_search(big, small) {
        Some(index) => println!("Match found starting at index {}", index),
        None => println!("No match found"),
    }
}

for i in 0..=big_chars.len().saturating_sub(small_chars.len()) {

try each possible start index in big word where small word can fit

for j in 0..small_chars.len() {

check each character of small word against big word starting at i

if big_chars[i + j] != small_chars[j] { matched = false; break; }

stop checking this start if any character mismatches

if matched { return Some(i); }

return index if full small word matched

Output

Match found starting at index 2

Complexity Analysis

Time: O(n*m) because for each of the n characters in big word, we may check up to m characters of small word

Space: O(n + m) because we store characters of both strings in vectors

vs Alternative: Naive search is simple but slow; advanced algorithms like KMP improve to O(n + m) by avoiding repeated checks

Edge Cases

small word is empty

Returns 0 immediately, meaning empty string matches at start

DSA Rust

if small_chars.is_empty() { return Some(0); }

small word longer than big word

No match found because small word cannot fit

DSA Rust

for i in 0..=big_chars.len().saturating_sub(small_chars.len())

no matching substring

Returns None indicating no match

DSA Rust

return None // no match found

When to Use This Pattern

When you need to find if one string appears inside another, try substring search by checking each possible start point.

Common Mistakes

Mistake: Not checking all possible start positions in the big word
Fix: Use a loop that tries every valid start index where the small word can fit

Mistake: Not handling empty small word case
Fix: Add a check to return 0 if small word is empty, as empty string matches at start

Summary

Find if a smaller string appears inside a bigger string by checking each possible starting position.

Use when you want to locate a substring inside a larger string in a straightforward way.

The key insight is to slide the small string along the big string and compare characters one by one.

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