String Pattern Matching Naive in DSA C

Mental Model

Check every possible place in the text to see if the pattern matches exactly.

Analogy: Like looking for a small picture in a big photo by sliding it over every spot and comparing pixel by pixel.

Text:  T -> h -> i -> s ->   -> i -> s ->   -> a ->   -> t -> e -> x -> t -> null
Pattern: P -> a -> t -> t -> e -> r -> n -> null
Try matching pattern starting at each text node.

Dry Run Walkthrough

Input: text: "abcxabcd", pattern: "abcd"

Goal: Find the first position in text where pattern "abcd" appears exactly.

Step 1: Check pattern starting at text index 0

text: a[0] b c x a b c d
pattern: a b c d
compare text[0] and pattern[0]

Why: Start matching pattern from the first character of text

Step 2: Compare text[1] and pattern[1]

text: a b[1] c x a b c d
pattern: a b c d
matched 'a' and 'b' so far

Why: Continue matching next characters

Step 3: Compare text[2] and pattern[2]

text: a b c[2] x a b c d
pattern: a b c d
matched 'a','b','c' so far

Why: Continue matching next characters

Step 4: Compare text[3] and pattern[3]

text: a b c x[3] a b c d
pattern: a b c d
text[3] is 'x' but pattern[3] is 'd' - mismatch

Why: Mismatch found, stop matching here

Step 5: Shift pattern start to text index 1 and compare

text: a b c x a b c d
pattern: a b c d
compare text[1] and pattern[0]

Why: Try matching pattern starting at next text position

Step 6: Compare text[1] and pattern[0]

text: a b[1] c x a b c d
pattern: a b c d
text[1] is 'b' but pattern[0] is 'a' - mismatch

Why: Mismatch at first character, move to next position

Step 7: Shift pattern start to text index 2 and compare

text: a b c x a b c d
pattern: a b c d
compare text[2] and pattern[0]

Why: Try matching pattern starting at next text position

Step 8: Compare text[2] and pattern[0]

text: a b c[2] x a b c d
pattern: a b c d
text[2] is 'c' but pattern[0] is 'a' - mismatch

Why: Mismatch at first character, move to next position

Step 9: Shift pattern start to text index 3 and compare

text: a b c x a b c d
pattern: a b c d
compare text[3] and pattern[0]

Why: Try matching pattern starting at next text position

Step 10: Compare text[3] and pattern[0]

text: a b c x[3] a b c d
pattern: a b c d
text[3] is 'x' but pattern[0] is 'a' - mismatch

Why: Mismatch at first character, move to next position

Step 11: Shift pattern start to text index 4 and compare

text: a b c x a b c d
pattern: a b c d
compare text[4] and pattern[0]

Why: Try matching pattern starting at next text position

Step 12: Compare text[4] and pattern[0]

text: a b c x a[4] b c d
pattern: a b c d
matched 'a'

Why: First character matches, continue

Step 13: Compare text[5] and pattern[1]

text: a b c x a b[5] c d
pattern: a b c d
matched 'a','b'

Why: Continue matching next characters

Step 14: Compare text[6] and pattern[2]

text: a b c x a b c[6] d
pattern: a b c d
matched 'a','b','c'

Why: Continue matching next characters

Step 15: Compare text[7] and pattern[3]

text: a b c x a b c d[7]
pattern: a b c d
matched full pattern

Why: Full pattern matched, stop

Result:

text: a b c x a b c d
pattern: a b c d
Pattern found starting at index 4

Annotated Code

DSA C

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

// Naive pattern matching function
int naivePatternMatch(const char *text, const char *pattern) {
    int n = strlen(text);
    int m = strlen(pattern);

    for (int i = 0; i <= n - m; i++) {
        int j;
        for (j = 0; j < m; j++) {
            if (text[i + j] != pattern[j]) {
                break; // mismatch found, stop checking this position
            }
        }
        if (j == m) {
            return i; // pattern found at index i
        }
    }
    return -1; // pattern not found
}

int main() {
    const char text[] = "abcxabcd";
    const char pattern[] = "abcd";

    int index = naivePatternMatch(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++) {

try matching pattern starting at each text index

if (text[i + j] != pattern[j]) { break; }

stop checking current position on mismatch

if (j == m) { return i; }

pattern fully matched, return start index

Output

Pattern found at index 4

Complexity Analysis

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

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

vs Alternative: Compared to advanced algorithms like KMP which run in O(n+m), naive is simpler but slower for large inputs

Edge Cases

empty pattern

pattern matches at index 0 immediately

DSA C

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

pattern longer than text

no match found, returns -1

DSA C

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

pattern equals text

match found at index 0

DSA C

if (j == m) { return i; }

When to Use This Pattern

When you need to find if a small string appears inside a bigger string and no preprocessing is allowed, naive pattern matching is the first simple approach to try.

Common Mistakes

Mistake: Not stopping the inner loop on mismatch and continuing to compare unnecessary characters
Fix: Add a break statement immediately when a mismatch is found

Mistake: Looping beyond the valid range causing out-of-bound access
Fix: Ensure outer loop runs only until n - m to avoid overflow

Summary

It checks every possible position in the text to see if the pattern matches exactly.

Use it when you want a simple, easy-to-understand method for pattern searching without preprocessing.

The key insight is to slide the pattern over the text one by one and stop checking as soon as a mismatch occurs.