String Pattern Matching Naive in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to start the outer loop from the first character of the text.

DSA C

for (int i = 0; i <= n - m; i[1]) {
    // pattern matching logic
}

Drag options to blanks, or click blank then click option'

A++

B--

C+=

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using decrement operator -- causes the loop to run incorrectly.

Using '+=' without a value is invalid syntax.

The outer loop should increment i by 1 each time to check every possible starting position in the text.

2fill in blank

medium

Complete the code to compare characters of the pattern and text inside the inner loop.

DSA C

for (int j = 0; j < m; j++) {
    if (text[i + j] [1] pattern[j]) {
        break;
    }
}

Drag options to blanks, or click blank then click option'

A>

B==

C!=

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using '==' causes the loop to break on matching characters, which is wrong.

Using '>' or '<' compares ASCII values but is not suitable here.

We break the loop when characters do not match, so the condition should check for inequality.

3fill in blank

hard

Fix the error in the condition that checks if the pattern was found completely.

DSA C

if (j [1] m) {
    printf("Pattern found at index %d\n", i);
}

Drag options to blanks, or click blank then click option'

A==

B<

C>

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' or '<=' causes false positives before full match.

Using '>' is incorrect because j cannot be greater than m here.

If j equals m, it means all characters matched and the pattern is found.

4fill in blank

hard

Fill both blanks to correctly declare and initialize the lengths of text and pattern.

DSA C

int n = strlen([1]);
int m = strlen([2]);

Drag options to blanks, or click blank then click option'

Atext

Bpattern

Cstring

Dinput

Attempts:

3 left

💡 Hint

Common Mistakes

Using undefined variables like 'string' or 'input'.

Mixing up text and pattern variables.

We use strlen on the text and pattern strings to get their lengths.

5fill in blank

hard

Fill all three blanks to complete the naive pattern matching function header and variable declarations.

DSA C

void [1](char *[2], char *[3]) {
    int n = strlen(text);
    int m = strlen(pattern);
    // matching logic
}

Drag options to blanks, or click blank then click option'

AnaiveSearch

Btext

Cpattern

Dsearch

Attempts:

3 left

💡 Hint

Common Mistakes

Using incorrect function names like 'search'.

Swapping parameter names or using undefined names.

The function is named naiveSearch and takes text and pattern as parameters.

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