String Pattern Matching Naive in DSA C - Build from Scratch

String Pattern Matching Naive

📖 Scenario: You are building a simple text search tool that looks for a small pattern inside a larger text. This is like finding a word in a book by checking each letter one by one.

🎯 Goal: Build a program that uses the naive method to find all positions where a given pattern appears in a text string.

📋 What You'll Learn

Create a character array text with the exact value "abracadabra"

Create a character array pattern with the exact value "abra"

Create an integer variable text_length that stores the length of text

Create an integer variable pattern_length that stores the length of pattern

Use a nested for loop with variables i and j to check for pattern matches in text

Print all starting indices where pattern is found in text separated by spaces

💡 Why This Matters

🌍 Real World

Searching for keywords in documents, logs, or DNA sequences using simple matching.

💼 Career

Understanding basic string search algorithms is essential for roles in software development, data processing, and bioinformatics.

1

Create the text and pattern strings

Create a character array called text with the exact value "abracadabra" and a character array called pattern with the exact value "abra".

DSA C

# Your code here

Hint

Use double quotes to create string arrays in C.

2

Calculate lengths of text and pattern

Create an integer variable called text_length that stores the length of text using sizeof(text) - 1. Create an integer variable called pattern_length that stores the length of pattern using sizeof(pattern) - 1.

DSA C

#include 

char text[] = "abracadabra";
char pattern[] = "abra";

// Your code here

Hint

Use sizeof to get the size of the array including the null character, so subtract 1.

3

Implement the naive pattern matching logic

Use a for loop with variable i from 0 to text_length - pattern_length. Inside it, use another for loop with variable j from 0 to pattern_length to check if pattern[j] matches text[i + j]. If all characters match, print the index i followed by a space.

DSA C

#include 

char text[] = "abracadabra";
char pattern[] = "abra";

int text_length = sizeof(text) - 1;
int pattern_length = sizeof(pattern) - 1;

// Your code here

Hint

Use nested loops to compare each character of the pattern with the text starting at index i.

4

Print a newline after all matches

Add a printf statement to print a newline character \n after printing all matching indices.

DSA C

#include 

char text[] = "abracadabra";
char pattern[] = "abra";

int text_length = sizeof(text) - 1;
int pattern_length = sizeof(pattern) - 1;

int i, j;
for (i = 0; i <= text_length - pattern_length; i++) {
    for (j = 0; j < pattern_length; j++) {
        if (text[i + j] != pattern[j]) {
            break;
        }
    }
    if (j == pattern_length) {
        printf("%d ", i);
    }
}

// Your code here

Hint

Use printf("\n") to move to the next line after printing all matches.

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