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.