String Pattern Matching Naive in DSA C++

Mental Model

Check every possible place in the text to see if the pattern matches exactly.

Analogy: Like looking for a small word in a big book by reading every word and checking if the next words match the small word.

Text:  t  h  i  s  i  s  a  t  e  x  t  
Index: [0][1][2][3][4][5][6][7][8][9][10]
Pattern:  a  t
Pattern length = 2

Dry Run Walkthrough

Input: text: "thisisatext", pattern: "at"

Goal: Find all starting positions where pattern "at" appears in text

Step 1: Check text starting at index 0 for pattern

text: t h i s i s a t e x t
pattern: a t
checking text[0..1] = t h

Why: We start checking from the first character to see if pattern matches

Step 2: Check text starting at index 1 for pattern

text: t h i s i s a t e x t
pattern: a t
checking text[1..2] = h i

Why: Move one step forward to check next possible match

Step 3: Check text starting at index 6 for pattern

text: t h i s i s a t e x t
pattern: a t
checking text[6..7] = a t

Why: Found characters matching pattern, verify full pattern

Step 4: Pattern matches at index 6

text: t h i s i s a t e x t
pattern: a t
match found at index 6

Why: All characters matched, record this position

Result:

text: t h i s i s a t e x t
pattern: a t
match found at index 6

Annotated Code

DSA C++

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

using namespace std;

vector<int> naivePatternMatch(const string &text, const string &pattern) {
    vector<int> matches;
    int n = (int)text.size();
    int m = (int)pattern.size();
    for (int i = 0; i <= n - m; i++) {
        int j = 0;
        // Check if pattern matches starting at i
        while (j < m && text[i + j] == pattern[j]) {
            j++;
        }
        if (j == m) {
            matches.push_back(i); // pattern found at index i
        }
    }
    return matches;
}

int main() {
    string text = "thisisatext";
    string pattern = "at";
    vector<int> result = naivePatternMatch(text, pattern);
    for (int idx : result) {
        cout << "Match found at index " << idx << "\n";
    }
    if (result.empty()) {
        cout << "No match found\n";
    }
    return 0;
}

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

iterate over each possible start position in text

while (j < m && text[i + j] == pattern[j]) {

check character by character if pattern matches text at position i

if (j == m) {

if full pattern matched, record the start index

Output

Match found at index 6

Complexity Analysis

Time: O(n*m) because for each of the n-m+1 positions in text, we compare up to m characters of pattern

Space: O(k) where k is number of matches found, for storing match indices

vs Alternative: Naive is slower than advanced algorithms like KMP which run in O(n+m) by avoiding repeated comparisons

Edge Cases

empty pattern

matches at every index including end of text

DSA C++

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

pattern longer than text

no matches found, loop does not run

DSA C++

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

pattern equals text

one match at index 0 if equal, else no match

DSA C++

if (j == m) {

When to Use This Pattern

When you need to find if a small string appears inside a bigger string and no advanced preprocessing is required, use naive pattern matching to check all positions.

Common Mistakes

Mistake: Stopping the inner check too early without verifying full pattern
Fix: Ensure inner loop checks all characters until mismatch or full pattern length

Mistake: Looping beyond text length causing out-of-bound access
Fix: Limit outer loop to n - m to avoid overflow

Summary

It finds all places where a pattern appears in a text by checking every possible position.

Use it when you want a simple, easy-to-understand method for pattern searching without extra preprocessing.

The key is to compare the pattern fully at each position before moving on.

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