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?

It 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

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

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 each character of the pattern.

beginner

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

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

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

Because it may repeatedly check the same characters multiple times, leading to a high number of comparisons especially when the pattern and text have many repeated characters.

beginner

Show the output positions where the pattern "aba" appears in the text "ababcaba" using naive string matching.

The pattern "aba" appears at positions 0, 2, and 5 in the text "ababcaba".

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 the search immediately

C Shifts the pattern by the length of the pattern

D Skips to the next character in the 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(n + m)

B O(m^2)

C O(n^2)

D O(m * n)

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

If the text is "aaaaaa" and the pattern is "aaa", how many times will the naive algorithm check the pattern?

A 6 times

B 4 times

C 3 times

D 1 time

The pattern of length 3 can start at positions 0,1,2,3 in the text of length 6, so 4 checks.

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

A It requires extra memory for preprocessing

B It can skip some matches

C It may perform many redundant comparisons

D It only works for numeric patterns

The naive algorithm may perform many redundant comparisons, especially with repeated characters.

In naive string matching, if the pattern length is greater than the text length, what happens?

A No matches are found

B The algorithm finds matches at every position

C The algorithm crashes

D The pattern is truncated

If the pattern is longer than the text, no matches can be found.

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

Think about checking each position in the text one by one.

Describe the main limitations of the naive string pattern matching algorithm and why more advanced algorithms are used.

Consider performance and repeated work.

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