String Pattern Matching Naive in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to get the length of the pattern string.

DSA C++

int m = [1].length();

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

Aresult

Btext

Cpattern

Dindex

Attempts:

3 left

💡 Hint

Common Mistakes

Using the length of the text instead of the pattern.

Using an undefined variable.

We need the length of the pattern string to know how many characters to compare.

2fill in blank

medium

Complete the code to loop through the text string for possible pattern matches.

DSA C++

for (int i = 0; i <= n - [1]; i++) {

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

Aresult

Bi

Cn

Dm

Attempts:

3 left

💡 Hint

Common Mistakes

Looping until n instead of n - m.

Using the wrong variable in the loop condition.

We loop until the last possible start index where the pattern can fit in the text, which is n - m.

3fill in blank

hard

Fix the error in the inner loop condition to compare characters correctly.

DSA C++

for (int j = 0; j < [1]; j++) {

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

Am

Bn

Ci

Dresult

Attempts:

3 left

💡 Hint

Common Mistakes

Using the text length n instead of pattern length m.

Using the outer loop variable i inside the inner loop condition.

The inner loop should run for the length of the pattern (m) to compare each character.

4fill in blank

hard

Fill both blanks to check if characters match and break if they don't.

DSA C++

if (text[i + [1]] != pattern[[2]]) {
    break;
}

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

Aj

Bi

Cm

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variables for text and pattern indices.

Using outer loop variable i in pattern index.

We compare the character at text index i + j with pattern index j. If they differ, we break.

5fill in blank

hard

Fill all three blanks to print the match index when pattern is found.

DSA C++

if (j == [1]) {
    std::cout << "Pattern found at index " << [2] << std::endl;
    [3] = true;
}

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

Am

Bi

Cfound

Dj

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong variables for comparison or printing.

Not setting the found flag correctly.

When j equals m, the whole pattern matched. We print the index i and set found to true.

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