Substring Search Patterns in DSA C++ - Build from Scratch

Substring Search Patterns

📖 Scenario: Imagine you are building a simple text search tool that helps users find specific words inside a paragraph. This tool will look for a smaller piece of text (called a substring) inside a bigger text.

🎯 Goal: You will create a program that searches for all the positions where a given substring appears inside a larger string. This is useful for finding patterns or keywords in documents.

📋 What You'll Learn

Create a string variable for the main text

Create a string variable for the substring to search

Use a loop to check each possible position in the main text

Print all starting positions where the substring is found

💡 Why This Matters

🌍 Real World

Searching for keywords or patterns inside documents, logs, or messages is common in text editors, search engines, and data analysis tools.

💼 Career

Understanding substring search is fundamental for roles in software development, data processing, and quality assurance where text manipulation is frequent.

1

Create the main text string

Create a string variable called text and set it to the exact value "hello world, welcome to the world of programming".

DSA C++

# Your code here

Hint

Use std::string to create the variable text and assign the given sentence.

2

Create the substring to search

Add a string variable called pattern and set it to the exact value "world".

DSA C++

#include 
#include 

int main() {
    std::string text = "hello world, welcome to the world of programming";
    std::string pattern = "world";
    // Your code here
    return 0;
}

Hint

Create the pattern string just like you did for text.

3

Find all positions of the substring

Use a for loop with an integer variable i from 0 to text.length() - pattern.length(). Inside the loop, use text.substr(i, pattern.length()) == pattern to check if the substring matches. If it matches, print i followed by a space.

DSA C++

#include 
#include 

int main() {
    std::string text = "hello world, welcome to the world of programming";
    std::string pattern = "world";
    // Use a for loop to check each position
    // Print positions where substring matches
    // Your code here
    return 0;
}

Hint

Loop through text and compare each substring of length equal to pattern with pattern.

4

Print the final output

Add a std::cout statement after the loop to print a newline character \n for clean output.

DSA C++

#include 
#include 

int main() {
    std::string text = "hello world, welcome to the world of programming";
    std::string pattern = "world";
    for (int i = 0; i <= (int)text.length() - (int)pattern.length(); i++) {
        if (text.substr(i, pattern.length()) == pattern) {
            std::cout << i << " ";
        }
    }
    // Print a newline character
    // Your code here
    return 0;
}

Hint

Use std::cout << "\n"; to move to the next line after printing all positions.

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