Substring Search Patterns in DSA C++

Mental Model

Find if a small word or pattern appears inside a bigger text by checking each part step by step.

Analogy: Like looking for a small sticker on a long ribbon by sliding your eyes along the ribbon until you find the sticker.

Text: H -> E -> L -> L -> O ->   -> W -> O -> R -> L -> D -> null
Pattern: L -> L -> O -> null
↑ (start of text)
↑ (start of pattern)

Dry Run Walkthrough

Input: text: "HELLO WORLD", pattern: "LLO"

Goal: Find if the pattern "LLO" appears in the text and where it starts.

Step 1: Check text starting at index 0: compare 'H' with 'L'

Text: H[0] -> E[1] -> L[2] -> L[3] -> O[4] ->   -> W -> O -> R -> L -> D -> null
Pattern: L[0] -> L[1] -> O[2] -> null
No match at index 0

Why: First character does not match, so move to next index

Step 2: Check text starting at index 1: compare 'E' with 'L'

Text: H -> E[1] -> L -> L -> O ->   -> W -> O -> R -> L -> D -> null
Pattern: L -> L -> O -> null
No match at index 1

Why: First character does not match, so move to next index

Step 3: Check text starting at index 2: compare 'L' with 'L', then next characters

Text: H -> E -> L[2] -> L[3] -> O[4] ->   -> W -> O -> R -> L -> D -> null
Pattern: L[0] -> L[1] -> O[2] -> null
Match found at index 2

Why: All characters of pattern match text starting at index 2

Result:

Text: H -> E -> L[2] -> L -> O ->   -> W -> O -> R -> L -> D -> null
Pattern found starting at index 2

Annotated Code

DSA C++

#include <iostream>
#include <string>

// Function to find the first occurrence of pattern in text
int substring_search(const std::string& text, const std::string& pattern) {
    int n = text.size();
    int m = pattern.size();
    for (int i = 0; i <= n - m; i++) {
        int j = 0;
        // Check each character of pattern
        while (j < m && text[i + j] == pattern[j]) {
            j++;
        }
        if (j == m) {
            return i; // pattern found at index i
        }
    }
    return -1; // pattern not found
}

int main() {
    std::string text = "HELLO WORLD";
    std::string pattern = "LLO";
    int index = substring_search(text, pattern);
    if (index != -1) {
        std::cout << "Pattern found starting at index " << index << std::endl;
    } else {
        std::cout << "Pattern not found" << std::endl;
    }
    return 0;
}

for (int i = 0; i <= n - m; i++) {

slide the start position along the text to check each possible substring

while (j < m && text[i + j] == pattern[j]) {

compare characters one by one to check if pattern matches at current position

if (j == m) {

if all characters matched, pattern found at index i

Output

Pattern found starting at index 2

Complexity Analysis

Time: O(n*m) because in worst case we check each position in text and compare up to m characters of pattern

Space: O(1) because no extra space proportional to input size is used

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

Edge Cases

empty pattern

pattern is found at index 0 immediately

DSA C++

for (int i = 0; i <= n - m; i++) {

pattern longer than text

loop does not run, returns -1 meaning pattern not found

DSA C++

for (int i = 0; i <= n - m; i++) {

pattern not in text

all positions checked, returns -1

DSA C++

return -1; // pattern not found

When to Use This Pattern

When you need to find if a small string appears inside a bigger string, try substring search patterns starting with naive sliding window approach.

Common Mistakes

Mistake: Not checking all possible start positions in text, stopping too early
Fix: Make sure to loop from 0 to n - m inclusive to cover all possible positions

Mistake: Comparing characters without checking pattern length, causing out-of-bound errors
Fix: Use condition j < m in while loop to avoid accessing beyond pattern length

Summary

It finds if and where a smaller string appears inside a bigger string by checking each possible position.

Use it when you want to locate a pattern inside text in simple cases or as a base for more advanced methods.

The key insight is to slide along the text and compare characters one by one until a full match is found.

Practice

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

easy

A. To count the number of vowels in a string

B. To sort the characters of a string alphabetically

C. To reverse the entire string

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

Solution

1. Step 1: Understand substring search purpose

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

2. Step 2: Compare options with definition

   Only To find if a smaller string exists inside a larger string describes finding a smaller string inside a larger one, which matches substring search.

3. Final Answer:

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

4. Quick Check:

   Substring search = find smaller string inside larger [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 instead of finding patterns

2. Which of the following is the correct syntax to check if string pattern is a substring of string text in C++?

easy

A. if (text.find(pattern) != std::string::npos) { /* found */ }

B. if (pattern.contains(text)) { /* found */ }

C. if (text.indexOf(pattern)) { /* found */ }

D. if (text.search(pattern) == true) { /* found */ }

Solution

1. Step 1: Recall C++ substring search syntax

   In C++, std::string::find returns the position of the substring or std::string::npos if not found.

2. Step 2: Analyze each option

   if (text.find(pattern) != std::string::npos) { /* found */ } uses text.find(pattern) != std::string::npos, which is correct. Others use invalid or non-existent methods.

3. Final Answer:

   if (text.find(pattern) != std::string::npos) { /* found */ } -> Option A

4. Quick Check:

   Use find() and compare with npos [OK]

Hint: Use text.find(pattern) != npos to check substring [OK]

Common Mistakes:

• Using methods like contains or indexOf which don't exist in std::string
• Comparing find() result directly to true or false

3. What will be the output of the following C++ code?

std::string text = "hello world";
std::string pattern = "world";
size_t pos = text.find(pattern);
if (pos != std::string::npos) {
    std::cout << pos << std::endl;
} else {
    std::cout << -1 << std::endl;
}

medium

A. 5

B. -1

C. 6

D. 0

Solution

1. Step 1: Find substring position in text

   The substring "world" starts at index 6 in "hello world" (counting from 0).

2. Step 2: Check condition and output

   Since find returns 6 (not npos), the code prints 6.

3. Final Answer:

   6 -> Option C

4. Quick Check:

   "world" starts at index 6 in "hello world" [OK]

Hint: Remember string indices start at 0 in C++ [OK]

Common Mistakes:

• Counting index starting at 1 instead of 0
• Printing -1 when substring is actually found

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

std::string text = "example";
std::string pattern = "amp";
if (text.find(pattern) == -1) {
    std::cout << "Not found" << std::endl;
} else {
    std::cout << "Found" << std::endl;
}

medium

A. Comparing find() result to -1 instead of std::string::npos

B. Using std::cout incorrectly

C. Pattern string is empty

D. Missing semicolon after if statement

Solution

1. Step 1: Understand find() return value

   std::string::find returns std::string::npos if substring not found, not -1.

2. Step 2: Identify incorrect comparison

   Comparing to -1 is wrong; must compare to std::string::npos for correctness.

3. Final Answer:

   Comparing find() result to -1 instead of std::string::npos -> Option A

4. Quick Check:

   Use npos, not -1, to check find() failure [OK]

Hint: Always compare find() result with std::string::npos [OK]

Common Mistakes:

• Using -1 instead of std::string::npos for not found
• Assuming find() returns boolean

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

// Patterns: ["he", "she", "his", "hers"]
// Text: "ahishers"

hard

A. Use Rabin-Karp algorithm with hashing for each pattern

B. Build an Aho-Corasick automaton for all patterns and search once

C. Use naive search for each pattern separately

D. Use std::string::find in a loop for each pattern

Solution

1. Step 1: Understand multiple pattern search problem

   Searching many patterns separately is inefficient; better to search all at once.

2. Step 2: Identify best algorithm for multiple patterns

   Aho-Corasick builds a combined automaton to find all patterns in one pass efficiently.

3. Step 3: Compare other options

   Naive and Rabin-Karp per pattern or repeated find calls are slower for many patterns.

4. Final Answer:

   Build an Aho-Corasick automaton for all patterns and search once -> Option B

5. Quick Check:

   Multiple patterns = Aho-Corasick automaton [OK]

Hint: Use Aho-Corasick for multiple pattern substring search [OK]

Common Mistakes:

• Using naive search for each pattern separately
• Applying single-pattern algorithms repeatedly
• Ignoring combined automaton approach