Substring Search Patterns in DSA C#

Mental Model

Find if a smaller word appears inside a bigger word by checking each possible start point one by one.

Analogy: Like looking for a small sticker hidden inside a big book page by flipping through each line and checking carefully.

Big string: H -> E -> L -> L -> O -> W -> O -> R -> L -> D -> null
Pattern: L -> L -> O -> null
↑start points to each letter in big string to check

Dry Run Walkthrough

Input: big string: HELLOWORLD, pattern: LLO

Goal: Find if 'LLO' appears inside 'HELLOWORLD' and where it starts

Step 1: Check substring starting at index 0: HEL

H[0] E[1] L[2] L[3] O[4] W[5] O[6] R[7] L[8] D[9]

Why: Start checking from the first letter to see if pattern matches

Step 2: Check substring starting at index 1: ELL

H[0] E[1] L[2] L[3] O[4] W[5] O[6] R[7] L[8] D[9]

Why: Pattern did not match at index 0, move to next start point

Step 3: Check substring starting at index 2: LLO

H[0] E[1] L[2] L[3] O[4] W[5] O[6] R[7] L[8] D[9]

Why: Check if pattern matches starting here

Step 4: Pattern matches at index 2

H[0] E[1] L[2] L[3] O[4] W[5] O[6] R[7] L[8] D[9]

Why: All letters of pattern matched in sequence

Result:

Pattern 'LLO' found starting at index 2 in 'HELLOWORLD'

Annotated Code

DSA C#

using System;

class SubstringSearch {
    public static int FindSubstring(string text, string pattern) {
        int n = text.Length;
        int m = pattern.Length;
        if (m == 0) return 0; // empty pattern found at start
        for (int i = 0; i <= n - m; i++) {
            int j = 0;
            while (j < m && text[i + j] == pattern[j]) {
                j++;
            }
            if (j == m) {
                return i; // pattern found at index i
            }
        }
        return -1; // pattern not found
    }

    static void Main() {
        string text = "HELLOWORLD";
        string pattern = "LLO";
        int index = FindSubstring(text, pattern);
        if (index != -1) {
            Console.WriteLine($"Pattern '{pattern}' found starting at index {index} in '{text}'");
        } else {
            Console.WriteLine($"Pattern '{pattern}' not found in '{text}'");
        }
    }
}

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

Check each possible start position in text where pattern can fit

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

Compare characters one by one to see if pattern matches here

if (j == m) {

If all characters matched, pattern found at index i

Output

Pattern 'LLO' found starting at index 2 in 'HELLOWORLD'

Complexity Analysis

Time: O(n*m) because for each of the n-m+1 start points, we compare up to m characters

Space: O(1) because no extra space is used except variables

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

Edge Cases

Empty pattern string

Returns 0 because empty pattern is found at start by definition

DSA C#

if (m == 0) return 0;

Pattern longer than text

Returns -1 immediately because pattern cannot fit

DSA C#

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

Pattern not present in text

Returns -1 after checking all positions

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 search for simplicity.

Common Mistakes

Mistake: Not checking all possible start positions up to n - m
Fix: Loop from 0 to n - m inclusive to cover all valid start points

Mistake: Stopping comparison too early or not comparing characters one by one
Fix: Use a nested loop or while to compare each character until mismatch or full match

Summary

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

Use it when you want to locate a pattern inside text without extra preprocessing.

The key insight is to check every possible position and compare characters one by one until a full match or mismatch.

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