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?

No→Move to next index

↓

Reached end of text?

↓

Return match index

Start checking from the first character of the text. Compare the substring with the current segment. If it matches, return the index. If not, move one step forward and repeat until the end.

Execution Sample

DSA C#

string text = "hello world";
string pattern = "lo";
for (int i = 0; i <= text.Length - pattern.Length; i++) {
  if (text.Substring(i, pattern.Length) == pattern) {
    Console.WriteLine(i);
    break;
  }
}

This code searches for the substring "lo" in "hello world" and prints the starting index of the first match.

Execution Table

Step	Operation	Current Index (i)	Text Segment Compared	Match?	Action	Output
1	Compare substring with text segment	0	"he"	No	Move to next index
2	Compare substring with text segment	1	"el"	No	Move to next index
3	Compare substring with text segment	2	"ll"	No	Move to next index
4	Compare substring with text segment	3	"lo"	Yes	Print index and break	3
5	Exit loop	-	-	-	Substring found, stop searching

💡 Loop stops after finding substring at index 3.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
i	0	1	2	3	-	3
Text Segment	"he"	"el"	"ll"	"lo"	-	"lo"
Match Found	False	False	False	True	True	True

Key Moments - 3 Insights

Why does the loop run only until text.Length - pattern.Length?

Because checking beyond that would cause the substring to go past the text end. See execution_table rows 1-4 where i stops at 3 for pattern length 2.

Why do we break the loop after finding the first match?

Because the problem is to find the first occurrence only. The break in execution_table row 4 stops further checks.

What happens if the substring is not found?

The loop completes without printing anything, as no match is found. This is shown by absence of 'Yes' in the Match? column.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'i' when the substring matches?

A 2

B 3

C 1

D 0

💡 Hint

Check the 'Current Index (i)' and 'Match?' columns in execution_table row 4.

At which step does the loop stop searching?

A Step 3

B Step 5

C Step 4

D Step 2

💡 Hint

Look at the 'Action' and 'Output' columns where the break happens after a match.

If the pattern was "world", how would the loop's last index 'i' change?

A It would stop at 6

B It would stop at 5

C It would stop at 7

D It would stop at 4

💡 Hint

Calculate text.Length (11) - pattern.Length (5) = 6, which is the last index checked.

Concept Snapshot

Substring Search Pattern:
- Start from index 0 in text
- Compare substring length segment at each index
- If match found, return index and stop
- Loop runs until text.Length - pattern.Length
- Simple and direct substring matching approach

Full Transcript

This visualization shows how substring search works by checking each possible position in the text for the pattern. Starting at index 0, the code compares the substring segment with the pattern. If it matches, it prints the index and stops. If not, it moves forward by one index and repeats. The loop stops when the remaining text is shorter than the pattern. This method finds the first occurrence of the substring efficiently by direct comparison.

Practice

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

easy

A. To sort characters in a string alphabetically

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

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 options

   Sorting, reversing, and counting characters are different string operations unrelated to substring search.

3. Final Answer:

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

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
• Assuming substring search changes the string

2. Which of the following is the correct way to check if string text contains substring pattern in C#?

easy

A. bool found = Contains(text, pattern);

B. bool found = text.Find(pattern);

C. bool found = text.Contains(pattern);

D. bool found = text.Index(pattern);

Solution

1. Step 1: Recall C# string method for substring check

   The correct method to check if a string contains another is Contains, called on the string instance.

2. Step 2: Validate method usage

   text.Contains(pattern) returns a boolean indicating if pattern is inside text. Other options are invalid or do not exist.

3. Final Answer:

   bool found = text.Contains(pattern); -> Option C

4. Quick Check:

   Use Contains method on string to check substring [OK]

Hint: Use text.Contains(pattern) to check substring presence [OK]

Common Mistakes:

• Using non-existent methods like Find or Index
• Calling Contains as a standalone function
• Confusing method names or parameters

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

string text = "hello world";
string pattern = "wor";
bool result = text.Contains(pattern);
Console.WriteLine(result);

medium

A. True

B. Runtime exception

C. Compilation error

D. False

Solution

1. Step 1: Check if pattern "wor" is in text "hello world"

   The substring "wor" appears starting at index 6 in "hello world".

2. Step 2: Evaluate Contains method result

   Since the substring exists, text.Contains(pattern) returns true, so result is true.

3. Final Answer:

   True -> Option A

4. Quick Check:

   Substring "wor" in "hello world" = true [OK]

Hint: Check if substring is inside text literally to get true/false [OK]

Common Mistakes:

• Assuming Contains returns index instead of bool
• Thinking substring is not present due to partial match
• Confusing output with string printing

4. Identify the error in the following C# code snippet for substring search:

string text = "data structures";
string pattern = "struct";
int index = text.IndexOf(pattern);
if (index)
{
    Console.WriteLine("Found at " + index);
}

medium

A. The if condition should check if index >= 0

B. IndexOf method does not exist for strings

C. Pattern variable is not declared

D. Console.WriteLine syntax is incorrect

Solution

1. Step 1: Understand IndexOf return value

   IndexOf returns the starting index of the substring or -1 if not found.

2. Step 2: Check if condition usage

   The if condition if (index) is invalid because index is an int, not a boolean. It should check index >= 0 to confirm substring found.

3. Final Answer:

   The if condition should check if index >= 0 -> Option A

4. Quick Check:

   Check index >= 0 to confirm substring found [OK]

Hint: Check if index >= 0 to confirm substring found [OK]

Common Mistakes:

• Using int directly as boolean in if condition
• Assuming IndexOf returns boolean
• Ignoring negative index meaning not found

5. Given a list of strings words and a pattern string p, which approach best finds all words containing p as a substring efficiently in C#?

hard

A. Use words.IndexOf(p) directly

B. Sort the list and use binary search for the pattern

C. Replace all occurrences of p in each word with empty string

D. Use a loop to check each word with word.Contains(p) and collect matches

Solution

1. Step 1: Understand substring search in multiple strings

   To find all words containing p, we must check each word individually for the substring.

2. Step 2: Evaluate options for efficiency and correctness

   Using a loop with word.Contains(p) is straightforward and efficient. Sorting and binary search do not help substring search. words.IndexOf(p) is invalid because words is a list of strings, not a string. Replacing substrings does not find matches.

3. Final Answer:

   Use a loop to check each word with word.Contains(p) and collect matches -> Option D

4. Quick Check:

   Loop + Contains per word finds all substring matches [OK]

Hint: Loop through words and use Contains to find substring matches [OK]

Common Mistakes:

• Trying binary search for substring matching
• Using IndexOf on list instead of strings
• Replacing substrings instead of checking presence