String Pattern Matching Naive in DSA C++ - Execution Trace

Concept Flow - String Pattern Matching Naive

Start at text index i=0

↓

Check if pattern matches at i

↓

Record match

↓

Move i to i+1

→Check i < text length - pattern length + 1?

Yes↓

Repeat

No↓

End

The algorithm checks each position in the text to see if the pattern matches starting there, moving one step forward each time until the text end is reached.

Execution Sample

DSA C++

string text = "ABABAB";
string pattern = "ABA";
for(size_t i = 0; i <= text.length() - pattern.length(); i++) {
    if(text.substr(i, pattern.length()) == pattern) {
        cout << i << "\n";
    }
}

This code checks each possible position in the text to find where the pattern "ABA" appears.

Execution Table

Step	Operation	Text Index i	Pattern Check	Match Found	Visual State
1	Check pattern at i=0	0	text[0..2] = 'ABA' vs pattern 'ABA'	Yes	'ABA'BAB
2	Record match at i=0	0	-	Match at index 0	'ABA'BAB
3	Move to next index i=1	1	-	'BAB' vs 'ABA' no match	A'BAB'AB
4	Check pattern at i=1	1	text[1..3] = 'BAB' vs pattern 'ABA'	No	A'BAB'AB
5	Move to next index i=2	2	-	'ABA' vs 'ABA' match	AB'ABA'B
6	Check pattern at i=2	2	text[2..4] = 'ABA' vs pattern 'ABA'	Yes	AB'ABA'B
7	Record match at i=2	2	-	Match at index 2	AB'ABA'B
8	Move to next index i=3	3	-	'BAB' vs 'ABA' no match	ABA'BAB'
9	Check pattern at i=3	3	text[3..5] = 'BAB' vs pattern 'ABA'	No	ABA'BAB'
10	End	-	i=4 exceeds limit	-	Full text scanned

💡 i reaches 4, which is len(text) - len(pattern) + 1, so loop ends

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 5	After Step 7	After Step 9	Final
i	0	0	1	2	2	3	4
Match Found	No	Yes at 0	No	Yes at 2	Yes at 2	No	No

Key Moments - 3 Insights

Why do we stop checking when i reaches len(text) - len(pattern) + 1?

Because starting beyond that index, the pattern would not fit fully inside the text. See execution_table row 10 where i=4 ends the loop.

Why do we compare text substring text.substr(i, pattern.length()) with the pattern?

Because we want to check if the pattern exactly matches the text starting at position i. This is shown in execution_table rows 1, 4, 6, and 9.

Why do we move i by 1 each time instead of skipping ahead?

Because the naive method checks every position for a possible match, even if partial matches overlap. This is shown by i incrementing by 1 in rows 3, 5, 8.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of i when the second match is found?

A 2

B 1

C 3

D 0

💡 Hint

Check the 'Pattern Check' and 'Match Found' columns in rows 6 and 7.

At which step does the algorithm stop checking further positions?

A Step 8

B Step 10

C Step 5

D Step 3

💡 Hint

Look at the 'Operation' and 'Exit Note' describing loop termination.

If the pattern was "BAB" instead of "ABA", at which index would the first match be found according to the execution flow?

A 0

B 2

C 1

D 3

💡 Hint

Refer to the 'Pattern Check' column where 'BAB' is compared at i=1 and i=3.

Concept Snapshot

Naive String Pattern Matching:
- Check each index i in text from 0 to len(text)-len(pattern)
- Compare substring text.substr(i, pattern.length()) with pattern
- If match, record index i
- Move i by 1 each time
- Stops when pattern no longer fits in text

Full Transcript

The naive string pattern matching algorithm checks every possible position in the text to see if the pattern matches starting there. It starts at index 0 and compares the substring of the text with the pattern. If they match, it records the index. Then it moves one step forward and repeats until the pattern cannot fit anymore in the remaining text. This method is simple but can be slow for large texts and patterns.

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