String Pattern Matching Naive in DSA Python - Execution Trace

Concept Flow - String Pattern Matching Naive

Start at index i=0 in text

↓

Check if pattern matches text at i

↓

Record match

↓

i < text length - pattern length?

Yes↓

Repeat

No↓

End

The algorithm checks each position in the text to see if the pattern matches starting there, moving one by one until the end.

Execution Sample

DSA Python

text = "ABABAB"
pattern = "ABA"
for i in range(len(text) - len(pattern) + 1):
    if text[i:i+len(pattern)] == pattern:
        print(f"Pattern found at index {i}")

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

Execution Table

Step	Operation	Index i	Substring checked	Match?	Output
1	Check substring at i=0	0	"ABA"	Yes	Pattern found at index 0
2	Check substring at i=1	1	"BAB"	No
3	Check substring at i=2	2	"ABA"	Yes	Pattern found at index 2
4	Check substring at i=3	3	"BAB"	No
5	End	-	-	-	No more positions to check

💡 i reaches 4, which is beyond last possible start index (len(text)-len(pattern))

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
i	0	1	2	3	4	End
Substring checked	"ABA"	"BAB"	"ABA"	"BAB"	-	-
Match?	Yes	No	Yes	No	-	-

Key Moments - 3 Insights

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

Because beyond that point, the remaining text is shorter than the pattern, so a full match is impossible. See execution_table row 5.

Why do we compare text[i:i+len(pattern)] instead of just text[i]?

Because the pattern can be multiple characters long, we must compare the whole substring of the same length as the pattern. See execution_table rows 1-4.

What happens if the pattern is empty?

The loop runs from i=0 to len(text), and every substring of length 0 matches, so it would print a match at every position. This is a special case to handle separately.

Visual Quiz - 3 Questions

Look at the execution_table, what substring is checked at step 3?

A "AB"

B "BAB"

C "ABA"

D "BA"

💡 Hint

Check the 'Substring checked' column in execution_table row 3

At which step does the pattern NOT match the substring?

A Step 1

B Step 2

C Step 3

D Step 5

💡 Hint

Look at the 'Match?' column in execution_table rows 1-4

If the pattern was "BAB", at which index would the first match be found?

A 1

B 0

C 2

D 3

💡 Hint

Think about which substring equals "BAB" in the text "ABABAB"

Concept Snapshot

Naive String Pattern Matching:
- Check each index i in text from 0 to len(text)-len(pattern)
- Compare substring text[i:i+len(pattern)] with pattern
- If equal, record match at i
- Move i by 1 and repeat
- Stops when no more full pattern fits

Full Transcript

This visualization shows how the naive string pattern matching algorithm works by checking every possible position in the text to see if the pattern matches starting there. We start at index 0 and compare the substring of the text with the pattern. If they match, we print the index. Then we move to the next index and repeat until we reach the last possible start index where the pattern can fit. The execution table tracks each step, showing the substring checked and whether it matched. The variable tracker shows how the index and substring change over time. Key moments clarify why we stop early and why we compare substrings instead of single characters. The quiz tests understanding of these steps.