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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Naive Pattern Matching Positions

What is the output of the following C++ code that uses naive string pattern matching to find all occurrences of pattern "aba" in text "ababaaba"?

DSA C++

#include <iostream>
#include <vector>
#include <string>

std::vector<int> naivePatternMatch(const std::string &text, const std::string &pattern) {
    std::vector<int> positions;
    int n = text.size();
    int m = pattern.size();
    for (int i = 0; i <= n - m; i++) {
        int j = 0;
        while (j < m && text[i + j] == pattern[j]) {
            j++;
        }
        if (j == m) {
            positions.push_back(i);
        }
    }
    return positions;
}

int main() {
    std::string text = "ababaaba";
    std::string pattern = "aba";
    std::vector<int> result = naivePatternMatch(text, pattern);
    for (int pos : result) {
        std::cout << pos << " ";
    }
    return 0;
}

A 1 3 5

B 0 3 5

C 0 2 5

D 0 2 4

💡 Hint

Check each substring of length equal to pattern and compare character by character.

The pattern "aba" appears starting at indices 0 ("aba"), 2 ("aba"), and 5 ("aba") in the text "ababaaba".

🧠 Conceptual

intermediate

Number of Comparisons in Naive Pattern Matching

If the text length is 10 and the pattern length is 3, what is the maximum number of character comparisons the naive pattern matching algorithm will perform?

A 30

B 24

C 27

D 28

💡 Hint

Maximum comparisons happen when all characters match except the last one in each attempt.

The naive algorithm tries all possible starting positions (10 - 3 + 1 = 8). For each, it compares up to 3 characters. In worst case, 3 comparisons per position, total 8*3=24.

🔧 Debug

advanced

Identify the Error in Naive Pattern Matching Code

What error will the following code produce when run?

DSA C++

#include <iostream>
#include <string>

int main() {
    std::string text = "hello";
    std::string pattern = "lo";
    for (int i = 0; i < text.size() - pattern.size(); i++) {
        int j = 0;
        while (j < pattern.size() && text[i + j] == pattern[j]) {
            j++;
        }
        if (j == pattern.size()) {
            std::cout << i << std::endl;
        }
    }
    return 0;
}

A Prints 1

B Prints 2

C Runtime error (out_of_range)

D No output

💡 Hint

Check the loop condition for the last possible starting index.

The loop condition uses < instead of <=, so it misses the last valid starting index i=3 where "lo" matches in "hello". Hence, no output is printed.

❓ Predict Output

advanced

Output of Naive Pattern Matching with Overlapping Patterns

What is the output of the following code that finds all occurrences of pattern "aa" in text "aaaaa"?

DSA C++

#include <iostream>
#include <vector>
#include <string>

std::vector<int> naivePatternMatch(const std::string &text, const std::string &pattern) {
    std::vector<int> positions;
    int n = text.size();
    int m = pattern.size();
    for (int i = 0; i <= n - m; i++) {
        int j = 0;
        while (j < m && text[i + j] == pattern[j]) {
            j++;
        }
        if (j == m) {
            positions.push_back(i);
        }
    }
    return positions;
}

int main() {
    std::string text = "aaaaa";
    std::string pattern = "aa";
    std::vector<int> result = naivePatternMatch(text, pattern);
    for (int pos : result) {
        std::cout << pos << " ";
    }
    return 0;
}

A 0 1 2 3

B 0 2 4

C 1 2 3 4

D 0 1 2

💡 Hint

Check for overlapping matches carefully.

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

🧠 Conceptual

expert

Time Complexity of Naive Pattern Matching in Worst Case

What is the worst-case time complexity of the naive string pattern matching algorithm when text length is n and pattern length is m?

A O(n * m)

B O(n + m)

C O(n^2)

D O(m^2)

💡 Hint

Consider the nested loops: outer loop over text and inner loop over pattern.

The naive algorithm checks each position in text and compares up to m characters of pattern, leading to O(n*m) comparisons in 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 see if the pattern matches

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 pattern characters at each position

   At each position, it compares characters one by one until a mismatch or full match is found.

3. Final Answer:

   Check every possible position in the text to see if the pattern matches -> Option A

4. Quick Check:

   Naive = Check all positions [OK]

Hint: Naive means try all positions one by one [OK]

Common Mistakes:

• Thinking naive uses hashing
• Assuming pattern preprocessing is done
• Believing sorting helps in naive matching

2. Which of the following is the correct syntax to start a loop for naive pattern matching in C++ if text length is n and pattern length is m?

easy

A. for (int i = 0; i <= n - m; i++)

B. for (int i = 0; i < n; i++)

C. for (int i = 0; i < m; i++)

D. for (int i = 0; i <= n; i++)

Solution

1. Step 1: Determine valid start positions

   The pattern of length m can only start at positions 0 to n-m in the text to avoid overflow.

2. Step 2: Write loop condition

   The loop must run from i = 0 up to i <= n - m to cover all valid start indices.

3. Final Answer:

   for (int i = 0; i <= n - m; i++) -> Option A

4. Quick Check:

   Loop till n-m inclusive [OK]

Hint: Loop till n - m inclusive to avoid overflow [OK]

Common Mistakes:

• Looping till n causes out-of-bound errors
• Looping till m is too short
• Using < instead of <= misses last position

3. What will be the output of the following C++ code snippet?

std::string text = "abcabcabc";
std::string pattern = "abc";
int count = 0;
for (int i = 0; i <= text.size() - pattern.size(); i++) {
  int j = 0;
  while (j < pattern.size() && text[i + j] == pattern[j]) {
    j++;
  }
  if (j == pattern.size()) {
    count++;
  }
}
std::cout << count << std::endl;

medium

A. 0

B. 2

C. 1

D. 3

Solution

1. Step 1: Identify pattern occurrences

   The pattern "abc" appears at indices 0, 3, and 6 in the text "abcabcabc".

2. Step 2: Count matches in loop

   The loop checks each position and increments count when full pattern matches, resulting in count = 3.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Pattern occurs 3 times [OK]

Hint: Count matches by checking all valid start positions [OK]

Common Mistakes:

• Counting overlapping matches incorrectly
• Stopping after first match
• Off-by-one errors in loop range

4. Identify the bug in this naive pattern matching code snippet:

std::string text = "hellohello";
std::string pattern = "hello";
for (int i = 0; i < text.size() - pattern.size(); i++) {
  int j = 0;
  while (j < pattern.size() && text[i + j] == pattern[j]) {
    j++;
  }
  if (j == pattern.size()) {
    std::cout << "Pattern found at " << i << std::endl;
  }
}

medium

A. No bug, code is correct

B. Loop condition should be i <= text.size() - pattern.size()

C. text[i + j] should be pattern[j + i]

D. Pattern size comparison in while loop is wrong

Solution

1. Step 1: Check loop boundary

   The loop runs while i < text.size() - pattern.size(), which misses the last valid start position.

2. Step 2: Correct loop condition

   It should be i <= text.size() - pattern.size() to include the last possible match position.

3. Final Answer:

   Loop condition should be i <= text.size() - pattern.size() -> Option B

4. Quick Check:

   Include last start index with <= [OK]

Hint: Use <= to include last valid start index [OK]

Common Mistakes:

• Using < misses last match
• Swapping indices in comparison
• Assuming code is correct without boundary check

5. Given a text "ababababab" and pattern "abab", how many times will the naive algorithm find the pattern if it counts overlapping occurrences?

hard

A. 2

B. 3

C. 4

D. 5

Solution

1. Step 1: Identify all overlapping occurrences

   The pattern "abab" appears starting at indices 0, 2, 4, and 6 in the text "ababababab".

2. Step 2: Count total matches

   Counting all overlapping matches gives a total of 4 occurrences.

3. Final Answer:

   4 -> Option C

4. Quick Check:

   Overlapping matches count = 4 [OK]

Hint: Check every position, including overlaps [OK]

Common Mistakes:

• Ignoring overlapping matches
• Counting only non-overlapping occurrences
• Off-by-one errors in counting