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.

Practice

1. What is the main idea behind the naive string pattern matching algorithm?

easy

A. Sort the text and pattern before matching

B. Use a hash function to find the pattern quickly

C. Preprocess the pattern to skip some comparisons

D. Check every possible position in the text to see if the pattern matches

Solution

1. Step 1: Understand naive matching approach

   The naive algorithm tries to match the pattern starting at every position in the text.

2. Step 2: Compare with other methods

   Other methods use hashing or preprocessing, but naive does not.

3. Final Answer:

   Check every possible position in the text to see if the pattern matches -> Option D

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 is preprocessed
• Believing text is sorted before matching

2. Which of the following is the correct syntax to start checking pattern matching at index i in text using naive approach in Python?

easy

A. for j in range(len(pattern)): if text[i+j] != pattern[j]: break

B. for j in range(len(text)): if pattern[i+j] != text[j]: break

C. for i in range(len(pattern)): if text[j+i] != pattern[j]: break

D. for j in range(len(pattern)): if pattern[j] != text[j]: break

Solution

1. Step 1: Identify correct loop variables and indexing

   We loop over pattern length with j, compare text[i+j] with pattern[j].

2. Step 2: Check each option's indexing

   for j in range(len(pattern)): if text[i+j] != pattern[j]: break correctly uses text[i+j] and pattern[j]. Others mix indices or variables incorrectly.

3. Final Answer:

   for j in range(len(pattern)): if text[i+j] != pattern[j]: break -> Option A

4. Quick Check:

   Correct indexing = for j in range(len(pattern)): if text[i+j] != pattern[j]: break [OK]

Hint: Pattern index j matches text at i+j [OK]

Common Mistakes:

• Swapping text and pattern indices
• Using wrong loop variable
• Mixing i and j incorrectly

3. What will be the output of the following code?

text = "abracadabra"
pattern = "cada"
positions = []
for i in range(len(text) - len(pattern) + 1):
    match = True
    for j in range(len(pattern)):
        if text[i+j] != pattern[j]:
            match = False
            break
    if match:
        positions.append(i)
print(positions)

medium

A. [5]

B. [3]

C. [4]

D. []

Solution

1. Step 1: Check substring positions in text

   Pattern 'cada' length is 4. Check text from index 0 to 7 (11-4).

2. Step 2: Find matching index

   At index 4: text[4:8] = 'cada' matches pattern exactly.

3. Final Answer:

   [4] -> Option C

4. Quick Check:

   Match at index 4 only [OK]

Hint: Check substring slices matching pattern length [OK]

Common Mistakes:

• Off-by-one error in range
• Misreading substring indices
• Appending wrong index on match

4. The following code is intended to find all occurrences of a pattern in a text using naive matching. What is the bug?

text = "hellohello"
pattern = "llo"
positions = []
for i in range(len(text) - len(pattern)):
    match = True
    for j in range(len(pattern)):
        if text[i+j] != pattern[j]:
            match = False
            break
    if match:
        positions.append(i)
print(positions)

medium

A. The inner loop uses wrong indices for pattern

B. The range in outer loop misses last possible position

C. The match flag is reset incorrectly

D. Positions list is not initialized

Solution

1. Step 1: Analyze outer loop range

   Outer loop uses range(len(text) - len(pattern)) which excludes last valid start index.

2. Step 2: Correct range to include last position

   It should be range(len(text) - len(pattern) + 1) to check all positions.

3. Final Answer:

   The range in outer loop misses last possible position -> Option B

4. Quick Check:

   Loop range off by one [OK]

Hint: Outer loop must cover all start indices [OK]

Common Mistakes:

• Using range without +1
• Confusing inner loop indices
• Not resetting match flag properly

5. Given a text and a pattern, how can you modify the naive string pattern matching algorithm to count overlapping occurrences of the pattern in the text? For example, in text = "aaaaa" and pattern = "aaa", the count should be 3.

hard

A. After finding a match at index i, continue checking from i+1 instead of i+len(pattern)

B. Skip checking overlapping indices by moving i by len(pattern) after a match

C. Use a hash function to detect overlaps

D. Reverse the text and pattern before matching

Solution

1. Step 1: Understand overlapping matches

   Overlapping means matches can start before previous match ends.

2. Step 2: Modify iteration after match

   Instead of skipping ahead by pattern length, move only one step forward to catch overlaps.

3. Final Answer:

   After finding a match at index i, continue checking from i+1 instead of i+len(pattern) -> Option A

4. Quick Check:

   Move one step after match for overlaps [OK]

Hint: Move one step after match to count overlaps [OK]

Common Mistakes:

• Skipping too far after match
• Using hashing unnecessarily
• Reversing strings without reason