String Pattern Matching Naive in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

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

The naive algorithm checks for the pattern at every possible position in the text by comparing characters one by one until a match is found or all positions are checked.

beginner

In the naive string pattern matching algorithm, what happens when a mismatch occurs during comparison?

When a mismatch occurs, the algorithm shifts the pattern by one position to the right in the text and starts comparing again from the first character of the pattern.

intermediate

What is the worst-case time complexity of the naive string pattern matching algorithm?

The worst-case time complexity is O(m * n), where m is the length of the pattern and n is the length of the text, because it may check every character of the text for every character of the pattern.

beginner

Show the output of the naive string pattern matching algorithm when searching for pattern "abc" in text "abcabcabc".

The pattern "abc" is found at positions 0, 3, and 6 in the text.

intermediate

Why is the naive string pattern matching algorithm not efficient for large texts and patterns?

Because it checks every possible position in the text and compares characters one by one without skipping, leading to many repeated comparisons especially when the pattern and text have repeated characters.

What does the naive string pattern matching algorithm do when it finds a mismatch?

A Shifts the pattern by one position and restarts comparison

B Stops searching immediately

C Skips multiple characters based on pattern

D Reverses the text and pattern

The naive algorithm shifts the pattern by one position to the right and starts comparing again from the first character.

What is the time complexity of the naive string pattern matching algorithm in the worst case?

A O(m * n)

B O(m + n)

C O(n)

D O(log n)

The worst-case time complexity is O(m * n), where m is pattern length and n is text length.

If the pattern length is 3 and text length is 10, how many maximum comparisons can the naive algorithm make?

A 10

B 3

C 13

D 24

Maximum comparisons = (text length - pattern length + 1) * pattern length = (10 - 3 + 1) * 3 = 8 * 3 = 24.

Which of these is a key disadvantage of the naive string pattern matching algorithm?

A It is complex to implement

B It can be slow for large inputs

C It requires extra memory

D It only works for numeric patterns

The naive algorithm can be slow because it checks every position without skipping.

What is the first step in the naive string pattern matching algorithm?

A Reverse the pattern

B Sort the text

C Compare pattern with text starting at position 0

D Calculate pattern hash

The algorithm starts by comparing the pattern with the text from position 0.

Explain how the naive string pattern matching algorithm works step-by-step.

Think about sliding the pattern over the text and checking each character.

Describe the time complexity of the naive string pattern matching algorithm and why it can be inefficient.

Consider how many times characters are compared in the worst case.

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