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

↓

Is i <= text length - pattern length?

Yes↓

Repeat

No↓

End

Start checking from each position in the text if the pattern matches fully. If yes, record match. Always move to next position. Repeat until no more positions to check.

Execution Sample

DSA C

text = "ABABAB"
pattern = "ABA"
for i in 0 to len(text)-len(pattern):
  check if text[i..i+len(pattern)-1] == pattern
  if yes, print i

This code checks each possible position in the text to see if the pattern appears starting there.

Execution Table

Step	Operation	Text Index i	Pattern Index j	Match So Far	Action	Matches Found	Visual State
1	Start checking at i=0	0	-	None	Check pattern at i=0	[]	Text: ABABAB Pattern: ABA Checking at i=0
2	Compare text[0] and pattern[0]	0	0	A == A	Continue	[]	A vs A: match
3	Compare text[1] and pattern[1]	0	1	B == B	Continue	[]	B vs B: match
4	Compare text[2] and pattern[2]	0	2	A == A	Full match	[]	A vs A: match
5	Pattern matched at i=0	0	2	Full match	Record match	[0]	Match at index 0
6	Increment i to 1	1	-	None	Check pattern at i=1	[0]	Checking at i=1
7	Compare text[1] and pattern[0]	1	0	B != A	Mismatch	[0]	B vs A: no match
8	Increment i to 2	2	-	None	Check pattern at i=2	[0]	Checking at i=2
9	Compare text[2] and pattern[0]	2	0	A == A	Continue	[0]	A vs A: match
10	Compare text[3] and pattern[1]	2	1	B == B	Continue	[0]	B vs B: match
11	Compare text[4] and pattern[2]	2	2	A == A	Full match	[0]	A vs A: match
12	Pattern matched at i=2	2	2	Full match	Record match	[0, 2]	Match at index 2
13	Increment i to 3	3	-	None	Check pattern at i=3	[0, 2]	Checking at i=3
14	Compare text[3] and pattern[0]	3	0	B != A	Mismatch	[0, 2]	B vs A: no match
15	Increment i to 4	4	-	None	Check pattern at i=4	[0, 2]	Checking at i=4
16	Compare text[4] and pattern[0]	4	0	A == A	Continue	[0, 2]	A vs A: match
17	Compare text[5] and pattern[1]	4	1	B == B	Continue	[0, 2]	B vs B: match
18	Compare text[6] and pattern[2]	4	2	Index out of range	Stop	[0, 2]	No character at text[6]
19	End checking, no more positions	-	-	-	-	[0, 2]	Matches found at indices 0 and 2

💡 i reached 4 which is text length - pattern length, no further full pattern check possible

Variable Tracker

Variable	Start	After Step 5	After Step 12	Final
i	0	0	2	4
j	-	2	2	-
Matches Found	[]	[0]	[0, 2]	[0, 2]

Key Moments - 3 Insights

Why do we stop checking when i reaches text length - pattern length + 1?

Because starting beyond that point, the pattern would not fit fully in the text. See execution_table row 18 where index 6 is out of range.

Why do we compare characters one by one instead of the whole substring at once?

Because naive matching checks each character to confirm a full match. Partial mismatch stops early. See rows 2-4 and 9-11 for character comparisons.

What happens when a mismatch occurs during pattern check?

We stop checking at that position and move to the next index i. See row 7 and 14 where mismatch causes increment of i.

Visual Quiz - 3 Questions

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

A 1

B 2

C 0

D 3

💡 Hint

Check the 'Matches Found' column and find when the second match is recorded (row 12).

At which step does the first mismatch occur during pattern checking?

A Step 7

B Step 14

C Step 18

D Step 3

💡 Hint

Look for the first 'Mismatch' action in the 'Action' column in execution_table.

If the pattern was "BAB" instead of "ABA", how would the matches found change?

A No matches found

B Matches at indices 0 and 2

C Matches at indices 1 and 3

D Matches at indices 2 and 4

💡 Hint

Think about where "BAB" appears in "ABABAB" and relate to the 'Matches Found' variable_tracker.

Concept Snapshot

Naive String Pattern Matching:
- Check each text index i from 0 to (text length - pattern length)
- Compare pattern characters one by one with text starting at i
- If all match, record i as a match
- If mismatch, move to next i
- Stops when no more full pattern fits in text

Full Transcript

Naive string pattern matching checks every possible position in the text to see if the pattern appears starting there. It compares characters one by one. If all characters match, it records the position. If a mismatch occurs, it moves to the next position. The process stops when the remaining text is shorter than the pattern. This method is simple but can be slow for large texts and patterns.