Substring Search Patterns in DSA Rust - Deep Dive

Overview - Substring Search Patterns

What is it?

Substring search finds all occurrences of a pattern string within a text string. The naive approach checks every position in O(n×m). Efficient algorithms like KMP and Rabin-Karp achieve O(n+m) by avoiding redundant comparisons. In Rust, str.contains(), str.find(), and manual byte-level iteration provide zero-cost abstractions for substring search.

Why it matters

Substring search is fundamental to text editors, search engines, log analysis, bioinformatics (DNA sequence matching), and compiler tokenization. Understanding the algorithmic tradeoffs between naive, KMP, and Rabin-Karp prepares you for both interview string problems and real systems work.

Where it fits

You need comfort with Rust string slices (&str), byte indexing, and UTF-8 encoding before tackling this. After mastering it, regex matching, KMP failure function, and Aho-Corasick multi-pattern search follow naturally.

Mental Model

Core Idea

Slide a window of pattern length across the text, checking for a match at each position. Efficient algorithms skip positions where a match is provably impossible.

Think of it like...

Searching for a word in a book by sliding a paper template (the pattern) across the page. Naive: shift one letter at a time. KMP: when mismatch occurs, skip ahead based on what we already matched — like knowing the next possible word start from partial information.

Text:    a b c a b c a b d
Pattern: a b c a b d

Naive: check pos 0,1,2,3,4,5,6...
Pos 0: abcabc vs abcabd → mismatch at pos 5
Pos 1: bcabc vs abcabd → immediate mismatch
...
Pos 3: abcabd vs abcabd → MATCH at pos 3 ✓

KMP: after mismatch at pos 5, jump forward using
failure function — skip to pos 3 directly

Build-Up - 5 Steps

1

Foundation

Naive Substring Search — O(n×m)

Concept: Check pattern match at every position in text.

For every starting position i in text (0 to n-m): compare text[i..i+m] with pattern. If all m characters match, record position i. Time O(n×m) — n positions × m comparison each. In Rust: for i in 0..=(text.len()-pat.len()) { if &text[i..i+pat.len()] == pat { positions.push(i); } }. Note: Rust's &str slices are byte-indexed — use .as_bytes() for character-level comparison to handle UTF-8 safely.

Result

Correct but slow baseline O(n×m) search.

The naive approach re-examines characters already known to match — KMP eliminates this by precomputing where to resume after a mismatch.

2

Foundation

Rust String Slicing — Bytes vs Characters

Concept: Rust strings are UTF-8 encoded — byte indexing differs from character indexing.

In Rust, text[i..j] slices bytes, not characters. For ASCII patterns, byte indexing works correctly. For Unicode patterns, use text.char_indices() to find character boundaries. str.find(pat) returns byte position of first match. str.match_indices(pat) returns iterator of all (byte_pos, &str) matches. For performance-critical code, work with &[u8] (byte slices) to avoid UTF-8 overhead.

Result

Understand when to use &str vs &[u8] for substring search in Rust.

Most DSA substring problems use ASCII — &[u8] byte comparison is both correct and faster than char-level comparison for ASCII inputs.

3

Intermediate

Rabin-Karp — Rolling Hash O(n+m)

🤔Before reading on: if you hash the pattern and the current window, how can you update the window hash in O(1) when the window slides one position? Commit to your approach.

Concept: Compute a rolling hash of the current window. Only do character comparison when hashes match.

Compute hash of pattern (h_pat) and first window (h_win). Slide: h_win = (h_win - text[i] × base^(m-1)) × base + text[i+m]. If h_win == h_pat: verify character by character (to handle hash collisions). Average O(n+m) — only O(1) character comparisons per collision. In Rust: use u64 arithmetic with modular reduction to prevent overflow. Choose a large prime modulus to minimize collisions.

Result

Average O(n+m) with O(1) rolling hash update per step.

Rolling hash is the key insight: removing the leftmost character and adding the rightmost takes O(1). Modular arithmetic prevents u64 overflow.

4

Intermediate

KMP — Failure Function O(n+m)

🤔Before reading on: if pattern is 'abcabc' and we matched 5 characters then hit a mismatch, how far back do we need to restart the comparison? Commit to your answer.

Concept: Precompute failure function: for each prefix of pattern, the length of the longest proper prefix that is also a suffix.

Build failure array fail[i] = length of longest proper prefix of pattern[0..i] that is also a suffix. Example: 'abcabc' → fail=[0,0,0,1,2,3]. During search: on mismatch at pattern[j], don't restart from 0 — restart from pattern[fail[j-1]]. This means we never re-examine text characters. Build failure function in O(m), search in O(n). Total O(n+m).

Result

Guaranteed O(n+m) worst-case — no re-examination of text characters.

The failure function encodes the 'self-overlap' structure of the pattern. When a mismatch occurs, we already know the longest prefix of pattern that matches the current suffix of what we've seen.

5

Advanced

Rust Standard Library — str.find() and str.match_indices()

🤔Before reading on: does Rust's str.find() use a naive or optimized algorithm internally? Commit to your guess.

Concept: Rust's standard library uses optimized SIMD-accelerated substring search.

Rust's str.contains(), str.find(), and str.match_indices() use a highly optimized algorithm (Two-Way algorithm or SIMD-based search) that achieves O(n/m) in practice for aligned patterns. For most production code, use these directly: text.find(pat) for first match, text.match_indices(pat).collect() for all positions. Only implement KMP or Rabin-Karp manually when you need guaranteed O(n+m) worst-case or need to customize the algorithm.

Result

Standard library methods are correct and fast for production — manual implementation is for learning and specialized cases.

Knowing the standard library uses optimized algorithms means you should reach for str.find() in production and only implement KMP when the interviewer specifically asks for it.

Under the Hood

KMP's correctness rests on the failure function: fail[i] tells us the longest border (prefix = suffix) of pattern[0..=i]. When pattern[j] mismatches text[i], we know text[i-j..i] matches pattern[0..j-1]. Since fail[j-1] is the longest prefix of pattern that is also a suffix of pattern[0..j-1], we can continue matching from pattern[fail[j-1]] without re-examining text[i]. This amortized O(n) traversal uses the fact that j can only increase n times total — every decrease in j corresponds to a previous increase.

Why designed this way?

KMP was designed to eliminate redundant comparisons. The failure function is built in O(m) using the same sliding principle applied to the pattern matching itself. Rabin-Karp trades worst-case guarantees for simpler implementation — the rolling hash update is O(1) while KMP's failure function requires careful implementation. Both achieve O(n+m) on average.

KMP failure function for 'abcabc':
Idx:  0 1 2 3 4 5
Pat:  a b c a b c
Fail: 0 0 0 1 2 3

Reading fail[5]=3 means:
'abc' (length 3) is both a prefix and suffix of 'abcabc'

Mismatch after matching 5 chars (pattern[5]):
→ Don't restart from 0
→ Restart from pattern[fail[4]] = pattern[2] = 'c'

Myth Busters - 2 Common Misconceptions

Quick: does str[i..j] in Rust access characters or bytes? Commit your answer.

Common Belief: str[i..j] accesses the ith through jth characters.

Reality: str[i..j] accesses bytes i through j-1. For multi-byte UTF-8 characters, this can panic if i or j falls inside a character boundary.

Why it matters: Using byte indices on Unicode strings causes runtime panics. Always use .char_indices() or .as_bytes() for safe indexed access in Rust.

Quick: is KMP always faster than naive search in practice? Commit yes or no.

Common Belief: KMP is always faster than naive search because of O(n+m) vs O(n×m).

Reality: For most practical text (natural language, code), naive search with early termination is very fast because mismatches occur at the first or second character most of the time. KMP shines on pathological inputs like 'aaaa...aaab' matching against 'aaa...aab'.

Why it matters: Over-engineering: using KMP for simple string search in production code adds complexity without practical speedup. Use str.find() or naive search unless proven to be a bottleneck.

Expert Zone

1

Rust's memchr crate provides SIMD-accelerated single-byte search — the fastest option for byte-level pattern searching in Rust.

2

For pattern matching with wildcards or regex, use the regex crate which implements a DFA-based matcher with O(n) guaranteed time per match.

3

The Two-Way string matching algorithm (used in Rust's standard library) achieves O(n/m) average time on aligned patterns using only O(1) extra space — superior to KMP's O(m) space for the failure function.

When NOT to use

Don't implement KMP or Rabin-Karp in production Rust — str.find() is faster due to SIMD optimization. Use KMP when you need to implement substring search from scratch (interview) or need a streaming/online algorithm that processes text one character at a time.

Production Patterns

Substring search appears in: log analysis (grep), text editors (Ctrl+F), bioinformatics (DNA motif search), network packet inspection, and compiler lexers. Each uses different tradeoffs: grep uses regex DFA, text editors use SIMD search, bioinformatics uses suffix arrays.

Connections

KMP Pattern Matching Algorithm

KMP is the canonical O(n+m) substring search algorithm — this DLM introduces the pattern; KMP's own DLM covers the failure function construction in depth.

Understanding the motivation for KMP (eliminating redundant comparisons) makes the failure function construction intuitive rather than magical.

Rabin-Karp String Matching

Rabin-Karp trades KMP's worst-case guarantee for simpler implementation via rolling hash — both achieve O(n+m) average.

Rabin-Karp extends naturally to multi-pattern search: compute hash of all patterns, then check each window against all pattern hashes in O(k) per window.

Common Pitfalls

#1 Byte-indexing a UTF-8 Rust string at non-boundary positions.

Wrong approach:

let s = "héllo";
let sub = &s[1..3]; // PANIC: byte 1 is inside 'é' (2-byte char)

Correct approach:

let s = "héllo";
// Use char_indices for safe character-level access
let chars: Vec = s.chars().collect();
// Or work with ASCII-only data as bytes:
let bytes = s.as_bytes();

Root cause:

Rust strings are UTF-8 where non-ASCII characters take 2-4 bytes. Slicing at a non-boundary byte index panics with 'byte index is not a char boundary'.

#2 Off-by-one in naive search loop bound.

Wrong approach:

for i in 0..text.len() - pat.len() { // WRONG: misses last valid position
if &text[i..i+pat.len()] == pat { ... }
}

Correct approach:

for i in 0..=(text.len() - pat.len()) { // Correct: inclusive upper bound
if &text[i..i+pat.len()] == pat { ... }
}

Root cause:

The last valid starting position is text.len() - pat.len() (inclusive). Using exclusive upper bound misses the final potential match position.

Key Takeaways

Naive search is O(n×m) — correct but inefficient for long patterns or many repetitions in text.

KMP and Rabin-Karp both achieve O(n+m) average — KMP by precomputing failure function, Rabin-Karp by rolling hash.

Rust's str.find() and str.match_indices() use SIMD-optimized algorithms — prefer these in production over manual KMP.

Rust strings are UTF-8 — always use .as_bytes() for byte-level ASCII search or .char_indices() for character-level Unicode search.

Off-by-one in loop bounds is the most common bug — the last valid window start is text.len() - pat.len() (inclusive).

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