Substring Search Patterns in DSA C

Mental Model

Find if a small word (pattern) appears inside a bigger word (text) by checking each position step-by-step.

Analogy: Like looking for a small sticker inside a big book page by sliding your finger along the page and checking each spot carefully.

Text:  H  E  L  L  O  W  O  R  L  D  \n       ↑\nPattern: L  L  O\n       ↑

Dry Run Walkthrough

Input: text: "HELLOWORLD", pattern: "LLO"

Goal: Find the starting index where pattern "LLO" appears in text "HELLOWORLD"

Step 1: Check text starting at index 0: compare 'H' with 'L'

Text: H E L L O W O R L D
       ↑
Pattern: L L O
         ↑

Why: Start checking from the first character of text

Step 2: Mismatch at first character, move to index 1

Text: H E L L O W O R L D
         ↑
Pattern: L L O
         ↑

Why: First character didn't match, try next position

Step 3: Compare text[1]='E' with pattern[0]='L', mismatch, move to index 2

Text: H E L L O W O R L D
           ↑
Pattern: L L O
           ↑

Why: Mismatch again, slide pattern forward

Step 4: Compare text[2]='L' with pattern[0]='L', match; check next chars

Text: H E L L O W O R L D
           ↑
Pattern: L L O
           ↑

Why: First character matches, check next characters

Step 5: Compare text[3]='L' with pattern[1]='L', match

Text: H E L L O W O R L D
             ↑
Pattern: L L O
             ↑

Why: Second character matches, continue

Step 6: Compare text[4]='O' with pattern[2]='O', match

Text: H E L L O W O R L D
               ↑
Pattern: L L O
               ↑

Why: Third character matches, pattern found

Result:

Pattern found starting at index 2 in text: H E [L L O] W O R L D

Annotated Code

DSA C

#include <stdio.h>
#include <string.h>

// Function to find pattern in text using simple substring search
int substring_search(const char *text, const char *pattern) {
    int n = strlen(text);
    int m = strlen(pattern);

    for (int i = 0; i <= n - m; i++) {
        int j = 0;
        // Check each character of pattern
        while (j < m && text[i + j] == pattern[j]) {
            j++;
        }
        if (j == m) {
            return i; // pattern found at index i
        }
    }
    return -1; // pattern not found
}

int main() {
    const char text[] = "HELLOWORLD";
    const char pattern[] = "LLO";

    int index = substring_search(text, pattern);
    if (index != -1) {
        printf("Pattern found at index %d\n", index);
    } else {
        printf("Pattern not found\n");
    }
    return 0;
}

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

slide pattern start position along text

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

compare characters one by one until mismatch or full match

if (j == m) {

if full pattern matched, return start index

Output

Pattern found at index 2

Complexity Analysis

Time: O(n*m) because for each of the n characters in text, we may compare up to m characters of pattern

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 comparisons

Edge Cases

Empty pattern string

Returns 0 immediately since empty pattern matches at start

DSA C

if (m == 0) return 0;

Pattern longer than text

Returns -1 immediately as no match possible

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 approach before optimizing.

Common Mistakes

Mistake: Not checking all possible start positions in text
Fix: Ensure loop runs until i <= n - m to cover all valid positions

Mistake: Stopping comparison too early without full pattern match
Fix: Use a loop to compare all characters of pattern before deciding match

Summary

Finds if and where a smaller string appears inside a bigger string by checking each position.

Use when you want to locate a pattern inside text in simple cases.

Slide the pattern along text and compare characters one by one until full match or mismatch.

Practice

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

easy

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

B. To sort the characters of a string alphabetically

C. To reverse the entire string

D. To count the total number of characters in a 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 A

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
• Mixing substring search with string length calculation

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)) { /* found */ }

B. if (text.contains(pattern)) { /* found */ }

C. if (pattern in text) { /* found */ }

D. if (strstr(text, pattern) != NULL) { /* found */ }

Solution

1. Step 1: Recall C substring search function

   In C, strstr() returns a pointer to the first occurrence of pattern in text, or NULL if not found.

2. Step 2: Check each option's syntax

   if (strstr(text, pattern) != NULL) { /* found */ } uses strstr correctly with NULL check. Options A, B, C use syntax from other languages or invalid in C.

3. Final Answer:

   if (strstr(text, pattern) != NULL) { /* found */ } -> Option D

4. Quick Check:

   C substring search uses strstr() [OK]

Hint: Use strstr() in C to find substring, check for NULL [OK]

Common Mistakes:

• Using methods from other languages like contains() or find()
• Not checking if strstr() returns NULL
• Confusing order of arguments in strstr()

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

char text[] = "hello world";
char *pos = strstr(text, "wor");
if (pos != NULL) {
    printf("%ld", pos - text);
} else {
    printf("-1");
}

medium

A. 6

B. 0

C. -1

D. 3

Solution

1. Step 1: Understand strstr() return value

   strstr(text, "wor") returns pointer to first occurrence of "wor" in "hello world", which starts at index 6.

2. Step 2: Calculate pointer difference

   Subtracting text pointer from pos gives index 6, which is printed.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Substring "wor" starts at index 6 [OK]

Hint: Pointer difference in strstr() gives substring start index [OK]

Common Mistakes:

• Printing pointer value instead of index difference
• Assuming substring starts at 0 or 3 incorrectly
• Not checking if strstr() returns NULL before subtracting

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

char *find_substring(char *text, char *pattern) {
    for (int i = 0; i <= strlen(text); i++) {
        if (strncmp(&text[i], pattern, strlen(pattern)) == 0) {
            return &text[i];
        }
    }
    return NULL;
}

medium

A. Function should return int index, not pointer

B. strncmp() is used incorrectly; should use strcmp() instead

C. The loop condition should be 'i < strlen(text) - strlen(pattern) + 1' to avoid overflow

D. No error; code works correctly

Solution

1. Step 1: Analyze loop boundary

   The loop runs from 0 to strlen(text), but comparing substrings beyond text length minus pattern length causes overflow.

2. Step 2: Correct loop condition

   Loop should run until i <= strlen(text) - strlen(pattern) to safely compare substrings of pattern length.

3. Final Answer:

   The loop condition should be 'i < strlen(text) - strlen(pattern) + 1' to avoid overflow -> Option C

4. Quick Check:

   Loop boundary must prevent substring overflow [OK]

Hint: Loop till text length minus pattern length to avoid overflow [OK]

Common Mistakes:

• Looping beyond valid substring start positions
• Using strcmp instead of strncmp for partial comparison
• Ignoring return type correctness

5. You want to find all occurrences of substring pat in string txt using C. Which approach correctly finds all start indices of pat in txt?

hard

A. Use strstr() once and return the first found position only

B. Use a loop with strstr() starting from last found position + 1 until strstr() returns NULL

C. Use strcmp() on entire text and pattern directly

D. Use strlen() to compare lengths and decide if substring exists

Solution

1. Step 1: Understand strstr() usage for multiple occurrences

   strstr() returns pointer to first occurrence. To find all, repeatedly call strstr() starting after last found position.

2. Step 2: Evaluate options

   Use a loop with strstr() starting from last found position + 1 until strstr() returns NULL correctly describes looping with strstr() advancing pointer. Use strstr() once and return the first found position only finds only first occurrence. Options C and D do not find all occurrences.

3. Final Answer:

   Use a loop with strstr() starting from last found position + 1 until strstr() returns NULL -> Option B

4. Quick Check:

   Loop with strstr() to find all occurrences [OK]

Hint: Loop with strstr() advancing pointer to find all matches [OK]

Common Mistakes:

• Using strstr() only once for all matches
• Using strcmp() which compares whole strings only
• Relying on length checks without searching