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".