Substring Search Patterns in DSA C++ - Execution Trace

Concept Flow - Substring Search Patterns

Start at index 0 in text

↓

Compare substring with text segment

↓

Match?

Yes→Record match position

No↓

Move to next index in text

↓

Reached end of text - substring length?

Yes→Stop

No↓

Repeat comparison

The search moves through the text, comparing the substring at each position until it finds matches or reaches the end.

Execution Sample

DSA C++

string text = "hellohello";
string pattern = "llo";
for (int i = 0; i <= text.size() - pattern.size(); i++) {
  if (text.substr(i, pattern.size()) == pattern) {
    cout << i << " ";
  }
}

This code searches for the substring "llo" in the text "hellohello" and prints all starting indices where it matches.

Execution Table

Step	Operation	Current Index (i)	Text Segment Compared	Match?	Output	Visual State
1	Compare substring with text segment	0	"hel"	No		hellohello
2	Compare substring with text segment	1	"ell"	No		hellohello
3	Compare substring with text segment	2	"llo"	Yes	2	hellohello
4	Compare substring with text segment	3	"loh"	No	2	hellohello
5	Compare substring with text segment	4	"ohe"	No	2	hellohello
6	Compare substring with text segment	5	"hel"	No	2	hellohello
7	Compare substring with text segment	6	"ell"	No	2	hellohello
8	Compare substring with text segment	7	"llo"	Yes	2 7	hellohello
9	Reached end of text - substring length	8		Stop	2 7	hellohello

💡 Index 8 exceeds text length minus pattern length, so search stops.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
i	0	0	1	2	3	4	5	6	7	8
Output	""	""	""	"2 "	"2 "	"2 "	"2 "	"2 "	"2 7 "	"2 7 "

Key Moments - 3 Insights

Why does the loop run only until i <= text.size() - pattern.size()?

Because comparing beyond that would cause substring extraction to go past the text end, which is invalid. See execution_table row 9 where index 8 stops the loop.

Why do we compare text.substr(i, pattern.size()) instead of just text[i]?

Because we need to compare the whole substring segment, not just one character. The execution_table shows full segments like "llo" compared at each step.

What happens if the substring is not found at all?

No matches are printed, and the output remains empty. The loop still runs through all valid indices as shown in steps 1, 2, 4, 5, 6, 7 where no match occurs.

Visual Quiz - 3 Questions

Look at the execution_table, what is the output after step 3?

A "2 "

B ""

C "7 "

D "2 7 "

💡 Hint

Check the Output column at step 3 in execution_table.

At which step does the substring match the text segment for the second time?

A Step 5

B Step 7

C Step 8

D Step 9

💡 Hint

Look for 'Yes' in the Match? column and the Output update in execution_table.

If the pattern was "hello", how would the number of loop iterations change?

A It would increase by 2

B It would decrease by 2

C It would stay the same

D It would decrease by 4

💡 Hint

Compare text.size() - pattern.size() for pattern lengths 3 and 5 in variable_tracker.

Concept Snapshot

Substring Search Patterns:
- Loop from i = 0 to text length - pattern length
- At each i, compare substring of length pattern.size()
- If match, record or print index
- Stop when no more valid positions
- Simple brute force search method

Full Transcript

This visualization shows how substring search works by sliding over the text and comparing segments to the pattern. The loop runs from index 0 up to the last possible start index where the pattern fits. At each step, the substring of the text is compared to the pattern. If they match, the index is printed. The process continues until the end of the text is reached. The variable tracker shows how the index and output change step by step. Key moments clarify why the loop limit is set and why full substring comparison is needed. The quiz tests understanding of output at specific steps and loop behavior with different pattern lengths.

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