Substring Search Patterns in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Naive Substring Search

What is the output of this Rust code that searches for all occurrences of a pattern in a text using a naive approach?

DSA Rust

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

fn main() {
    let text = "abracadabra";
    let pattern = "abra";
    let result = naive_search(text, pattern);
    println!("{:?}", result);
}

A [0, 7]

B [0, 3, 7]

C [3, 7]

D [7]

💡 Hint

Check where the substring "abra" appears exactly in the text "abracadabra".

The pattern "abra" appears at index 0 and again at index 7 in the text. The naive search checks all possible positions and collects these indices.

❓ Predict Output

intermediate

Output of KMP Prefix Table Construction

What is the output vector produced by the prefix function (also called lps array) for the pattern "ababc" in the KMP algorithm?

DSA Rust

fn compute_lps(pattern: &str) -> Vec<usize> {
    let m = pattern.len();
    let mut lps = vec![0; m];
    let mut len = 0;
    let mut i = 1;
    let chars: Vec<char> = pattern.chars().collect();
    while i < m {
        if chars[i] == chars[len] {
            len += 1;
            lps[i] = len;
            i += 1;
        } else {
            if len != 0 {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i += 1;
            }
        }
    }
    lps
}

fn main() {
    let pattern = "ababc";
    let lps = compute_lps(pattern);
    println!("{:?}", lps);
}

A [0, 1, 2, 3, 0]

B [0, 1, 0, 1, 2]

C [0, 0, 0, 1, 2]

D [0, 0, 1, 2, 0]

💡 Hint

The lps array stores the length of the longest proper prefix which is also suffix for each prefix of the pattern.

For "ababc", the lps array is [0,0,1,2,0]. This means at index 2, the longest prefix-suffix length is 1, at index 3 it is 2, and so on.

🔧 Debug

advanced

Identify the Error in Rabin-Karp Hash Calculation

What error does this Rust code produce when trying to compute the rolling hash for Rabin-Karp substring search?

DSA Rust

fn rabin_karp_hash(text: &str, pattern_len: usize) -> Vec<u64> {
    let base = 256u64;
    let prime = 101u64;
    let n = text.len();
    let mut hashes = Vec::new();
    let chars: Vec<u8> = text.bytes().collect();
    let mut hash = 0u64;
    let mut h = 1u64;

    for _ in 0..pattern_len - 1 {
        h = (h * base) % prime;
    }

    for i in 0..pattern_len {
        hash = (base * hash + chars[i] as u64) % prime;
    }

    hashes.push(hash);

    for i in pattern_len..n {
        hash = (base * (hash + prime - chars[i - pattern_len] as u64 * h % prime) + chars[i] as u64) % prime;
        hashes.push(hash);
    }

    hashes
}

fn main() {
    let text = "abcdabc";
    let hashes = rabin_karp_hash(text, 3);
    println!("{:?}", hashes);
}

A index out of bounds panic

B negative value in hash calculation causing wrong results

C panic at runtime due to integer overflow

D compilation error due to missing semicolon

💡 Hint

Look at the subtraction inside the rolling hash update and consider modular arithmetic properties.

The subtraction can produce a negative intermediate value before modulo, which in Rust with unsigned integers wraps around causing incorrect hash values.

🚀 Application

advanced

Choosing the Best Algorithm for Large Text and Small Pattern

You have a very large text and a very small pattern to search multiple times. Which substring search algorithm is best suited for this scenario?

A Naive search because it is simple and fast for small patterns

B Rabin-Karp because it uses hashing and is efficient for multiple pattern searches

C Boyer-Moore because it skips large parts of the text and is efficient for small patterns

D Knuth-Morris-Pratt (KMP) because it preprocesses the pattern for efficient searching

💡 Hint

Consider which algorithm can skip the most characters in the text when the pattern is small.

Boyer-Moore is efficient for small patterns in large texts because it uses bad character and good suffix heuristics to skip ahead, reducing comparisons.

🧠 Conceptual

expert

Time Complexity of KMP Algorithm

What is the worst-case time complexity of the Knuth-Morris-Pratt (KMP) substring search algorithm when searching a pattern of length m in a text of length n?

A O(n + m)

B O(n^2)

C O(n * log m)

D O(m * n)

💡 Hint

KMP preprocesses the pattern and then scans the text efficiently without backtracking.

KMP runs in linear time relative to the sum of the text and pattern lengths, O(n + m), by using the prefix table to avoid re-examining characters.

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