String Pattern Matching Naive in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Naive Pattern Matching on Simple Strings

What is the output of the following C code that uses naive pattern matching to find all occurrences of a pattern in a text?

DSA C

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

void naive_search(char *text, 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;
        }
        if (j == m)
            printf("%d ", i);
    }
}

int main() {
    char text[] = "ababcabcabababd";
    char pattern[] = "ababd";
    naive_search(text, pattern);
    return 0;
}

A No output

B 0 5 10

C 5 10

D 10

💡 Hint

Check where the pattern "ababd" fully matches in the text.

The pattern "ababd" appears only once starting at index 10 in the text. The naive search prints the starting indices of all matches.

❓ Predict Output

intermediate

Output when pattern is not present

What will be the output of this naive pattern matching code when the pattern does not exist in the text?

DSA C

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

void naive_search(char *text, 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;
        }
        if (j == m)
            printf("%d ", i);
    }
}

int main() {
    char text[] = "hello world";
    char pattern[] = "bye";
    naive_search(text, pattern);
    return 0;
}

A No output

B 0

C 11

D Error

💡 Hint

If the pattern is not found, the function prints nothing.

Since the pattern "bye" does not appear in "hello world", the loop never prints any index.

🧠 Conceptual

advanced

Time Complexity of Naive Pattern Matching

What is the worst-case time complexity of the naive pattern matching algorithm when searching a pattern of length m in a text of length n?

A O(n^2)

B O(n * m)

C O(n + m)

D O(m^2)

💡 Hint

Consider the nested loops: one over text and one over pattern.

The naive algorithm checks each position in the text and compares up to m characters, leading to O(n*m) in the worst case.

🔧 Debug

advanced

Identify the Bug in Naive Pattern Matching Code

What error will occur when running this naive pattern matching code?

DSA C

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

void naive_search(char *text, 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;
        }
        if (j == m)
            printf("%d ", i);
    }
}

int main() {
    char text[] = "abc";
    char pattern[] = "abc";
    naive_search(text, pattern);
    return 0;
}

A No output

B Infinite loop

C Segmentation fault

D Prints 0 3 6

💡 Hint

Check the loop boundary condition for i.

The loop runs from i = 0 to i <= n - m, which is correct and includes the last valid index n - m, so it will find the match at index 0.

🚀 Application

expert

Number of Matches Found by Naive Pattern Matching

Given the text "aaaaaa" and pattern "aaa", how many matches will the naive pattern matching algorithm find?

A 2

B 3

C 4

D 5

💡 Hint

Consider overlapping matches in the text.

The pattern "aaa" appears starting at indices 0, 1, 2, and 3 in the text "aaaaaa".

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