String Pattern Matching Naive in DSA Python - Build from Scratch

String Pattern Matching Naive

📖 Scenario: You are building a simple search tool that looks for a small word (pattern) inside a bigger text (string). This is like finding a word in a book page by checking each letter one by one.

🎯 Goal: Build a program that finds all starting positions where a given pattern appears in a text using the naive string matching method.

📋 What You'll Learn

Create a variable text with the exact string: 'ababcabcabababd'

Create a variable pattern with the exact string: 'ababd'

Create a list positions to store all starting indices where pattern is found in text

Use a naive approach to check every possible position in text for the pattern

Print the positions list at the end

💡 Why This Matters

🌍 Real World

Searching for words or phrases inside documents, logs, or any text data is a common task in text editors, search engines, and data analysis tools.

💼 Career

Understanding basic string matching helps in roles like software development, data analysis, and quality assurance where text processing is frequent.

1

Create the text and pattern variables

Create a variable called text and set it to the string 'ababcabcabababd'. Also create a variable called pattern and set it to the string 'ababd'.

DSA Python

# Create variables text and pattern with given strings
# Your code here

Hint

Use simple assignment to create text and pattern variables with the exact strings.

2

Create a list to store matching positions

Create an empty list called positions to store the starting indices where the pattern is found in text.

DSA Python

text = 'ababcabcabababd'
pattern = 'ababd'
# Create an empty list positions
# Your code here

Hint

Use [] to create an empty list named positions.

3

Implement naive pattern matching logic

Use a for loop with variable i to check every possible starting index in text where pattern could fit. Inside the loop, use another for loop with variable j to compare characters of pattern with text. If all characters match, append i to positions.

DSA Python

text = 'ababcabcabababd'
pattern = 'ababd'
positions = []
# Use nested loops to find all positions where pattern matches text
# Your code here

Hint

Check each position i in text where pattern can fit. Compare characters one by one. If all match, add i to positions.

4

Print the list of matching positions

Print the positions list to show all starting indices where the pattern was found in text.

DSA Python

text = 'ababcabcabababd'
pattern = 'ababd'
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 the positions list
# Your code here

Hint

Use print(positions) to show the result.

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