String Pattern Matching Naive in DSA C++ - Build from Scratch

String Pattern Matching Naive

📖 Scenario: You are building a simple text search tool that finds all positions where a small pattern appears inside a larger text. This is like looking for a word in a book page by page.

🎯 Goal: Build a program that uses the naive method to find all starting positions of a given pattern inside a given text string.

📋 What You'll Learn

Create a string variable text with the exact value "abracadabra".

Create a string variable pattern with the exact value "abra".

Create an integer variable n for the length of text and m for the length of pattern.

Use a for loop with variable i to check every possible starting index in text where pattern could match.

Use a nested for loop with variable j to compare characters of pattern with text starting at i.

If the pattern matches at position i, add i to a vector positions.

Print the positions vector showing all starting indices where the pattern occurs.

💡 Why This Matters

🌍 Real World

Searching for keywords or phrases inside documents, logs, or any text data is a common task in text editors, search engines, and data analysis tools.

💼 Career

Understanding basic string matching algorithms helps in roles like software development, data processing, and quality assurance where text search and pattern recognition are needed.

1

Create the text and pattern strings

Create a string variable called text with the value "abracadabra" and a string variable called pattern with the value "abra".

DSA C++

// Your code here

Hint

Use std::string to create the variables text and pattern with the exact given values.

2

Calculate lengths of text and pattern

Create integer variables n and m that store the lengths of text and pattern respectively.

DSA C++

#include 
#include 
#include 

int main() {
    std::string text = "abracadabra";
    std::string pattern = "abra";

    // Create variables n and m for lengths
    // Your code here

    return 0;
}

Hint

Use the length() method on text and pattern to get their sizes.

3

Find all positions where pattern matches text

Create a vector of integers called positions. Use a for loop with variable i from 0 to n - m. Inside it, use another for loop with variable j from 0 to m to compare pattern[j] with text[i + j]. If all characters match, add i to positions.

DSA C++

#include 
#include 
#include 

int main() {
    std::string text = "abracadabra";
    std::string pattern = "abra";

    int n = text.length();
    int m = pattern.length();

    // Create positions vector and find matches
    // Your code here

    return 0;
}

Hint

Use nested loops to compare each character of pattern with the corresponding character in text. If all match, add the index i to positions.

4

Print all matching positions

Use a for loop with variable pos to iterate over positions and print each position followed by a space.

DSA C++

#include 
#include 
#include 

int main() {
    std::string text = "abracadabra";
    std::string pattern = "abra";

    int n = text.length();
    int m = pattern.length();

    std::vector positions;

    for (int i = 0; i <= n - m; i++) {
        bool match = true;
        for (int j = 0; j < m; j++) {
            if (text[i + j] != pattern[j]) {
                match = false;
                break;
            }
        }
        if (match) {
            positions.push_back(i);
        }
    }

    // Print all positions
    // Your code here

    return 0;
}

Hint

Use a for loop to print each position in positions separated by spaces.

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