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.

Practice

1. What is the main idea behind the naive string pattern matching algorithm?

easy

A. Check every possible position in the text to find the pattern

B. Use a hash function to find the pattern quickly

C. Preprocess the pattern to skip some comparisons

D. Sort the text and pattern before matching

Solution

1. Step 1: Understand naive matching approach

   The naive algorithm tries to match the pattern starting at each position in the text one by one.

2. Step 2: Compare with other methods

   Other methods like hashing or preprocessing are not part of the naive approach.

3. Final Answer:

   Check every possible position in the text to find the pattern -> Option A

4. Quick Check:

   Naive = Check all positions [OK]

Hint: Naive means try all positions one by one [OK]

Common Mistakes:

• Confusing naive with hashing or preprocessing
• Thinking naive skips some positions
• Assuming sorting is involved

2. Which of the following is the correct syntax to start a loop for naive pattern matching in C to check each position in the text of length n for a pattern of length m?

easy

A. for (int i = 0; i < n; i++)

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

C. for (int i = 0; i < m; i++)

D. for (int i = 0; i <= n; i++)

Solution

1. Step 1: Determine loop range for pattern matching

   We must check positions where the pattern fits fully, so i goes from 0 to n - m inclusive.

2. Step 2: Check options

   for (int i = 0; i <= n - m; i++) correctly uses i <= n - m. Others either go beyond or do not cover all valid positions.

3. Final Answer:

   for (int i = 0; i <= n - m; i++) -> Option B

4. Quick Check:

   Loop till n - m inclusive [OK]

Hint: Loop till n - m to fit pattern fully [OK]

Common Mistakes:

• Looping till n instead of n - m
• Using < instead of <= causing missed checks
• Looping only till m

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

char text[] = "abcabcabc";
char pattern[] = "abc";
int n = 9, m = 3;
int count = 0;
for (int i = 0; i <= n - m; i++) {
    int j;
    for (j = 0; j < m; j++) {
        if (text[i + j] != pattern[j])
            break;
    }
    if (j == m) count++;
}
printf("%d\n", count);

medium

A. 1

B. 2

C. 0

D. 3

Solution

1. Step 1: Identify pattern matches in text

   Pattern "abc" appears at positions 0, 3, and 6 in the text "abcabcabc".

2. Step 2: Count matches

   Each match increments count, so total count is 3.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Pattern found 3 times [OK]

Hint: Count all exact matches by checking each position [OK]

Common Mistakes:

• Counting overlapping matches incorrectly
• Stopping after first match
• Off-by-one errors in loop

4. Identify the bug in the following naive pattern matching code snippet and choose the correct fix.

char text[] = "hellohello";
char pattern[] = "hello";
int n = 10, m = 5;
int count = 0;
for (int i = 0; i < n - m; i++) {
    int j;
    for (j = 0; j < m; j++) {
        if (text[i + j] != pattern[j])
            break;
    }
    if (j == m) count++;
}
printf("%d\n", count);

medium

A. Change loop condition to i <= n - m

B. Change inner loop to j <= m

C. Initialize count to 1

D. Use strcpy instead of comparison

Solution

1. Step 1: Analyze outer loop range

   The loop runs from i = 0 to i < n - m, which misses the last valid position at i = n - m.

2. Step 2: Fix loop condition

   Changing to i <= n - m ensures all valid positions are checked.

3. Final Answer:

   Change loop condition to i <= n - m -> Option A

4. Quick Check:

   Loop must include last valid index [OK]

Hint: Use <= n - m to include last valid start [OK]

Common Mistakes:

• Using < instead of <= in outer loop
• Changing inner loop incorrectly
• Misusing string functions for comparison

5. Given a text "abababab" and a pattern "aba", how many times will the naive pattern matching algorithm count the pattern occurrences including overlapping matches?

hard

A. 2

B. 5

C. 3

D. 4

Solution

1. Step 1: Identify all starting positions for pattern

   Text length n=8, pattern length m=3, so i from 0 to 5 inclusive.

2. Step 2: Check matches including overlaps

   Matches at positions 0 ("aba"), 2 ("aba"), and 4 ("aba") total 3 matches.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Count overlapping matches carefully [OK]

Hint: Check every position, count overlaps too [OK]

Common Mistakes:

• Ignoring overlapping matches
• Counting only non-overlapping occurrences
• Off-by-one errors in loop range