Why Substring Search Patterns in DSA C++?

The Big Idea

Discover how computers find your words instantly in huge texts without reading every letter!

The Scenario

Imagine you have a huge book and you want to find every place where a certain phrase appears. Doing this by reading every word and checking manually is like searching for a needle in a haystack.

The Problem

Manually scanning each word or letter is very slow and tiring. It is easy to miss some matches or make mistakes, especially if the phrase appears many times or overlaps with itself.

The Solution

Substring search patterns use smart ways to quickly find all places where a phrase appears in a text. They avoid checking the same parts again and again, making the search fast and reliable.

Before vs After

✗ Before

for (int i = 0; i <= (int)text.length() - (int)pattern.length(); i++) {
    bool found = true;
    for (int j = 0; j < (int)pattern.length(); j++) {
        if (text[i + j] != pattern[j]) {
            found = false;
            break;
        }
    }
    if (found) cout << "Found at " << i << endl;
}

✓ After

size_t index = text.find(pattern);
while (index != string::npos) {
    cout << "Found at " << index << endl;
    index = text.find(pattern, index + 1);
}

What It Enables

It enables fast and accurate searching of patterns inside large texts, making tasks like text editing, data analysis, and DNA sequencing possible.

Real Life Example

Search engines use substring search patterns to quickly find web pages containing your search words among billions of pages.

Key Takeaways

Manual search is slow and error-prone.

Substring search patterns speed up finding phrases in text.

They help in many real-world applications like search engines and text editors.

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