String Pattern Matching Naive in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if the pattern matches the text at position i.

DSA Python

if text[i:i+len(pattern)] == [1]:
    print(f"Pattern found at index {i}")

Drag options to blanks, or click blank then click option'

Apattern

Btext

Ctext[i]

Dpattern[i]

Attempts:

3 left

💡 Hint

Common Mistakes

Using text instead of pattern for comparison.

Comparing single characters instead of substrings.

We compare the substring of text starting at i with the pattern to check for a match.

2fill in blank

medium

Complete the code to iterate over all possible starting positions in the text.

DSA Python

for i in range(len(text) - [1] + 1):
    # check pattern match here

Drag options to blanks, or click blank then click option'

Alen(pattern) - 1

Blen(text)

Clen(text) - 1

Dlen(pattern)

Attempts:

3 left

💡 Hint

Common Mistakes

Using len(text) instead of len(pattern) in the range.

Off-by-one errors in the loop range.

We iterate until the last possible start where the pattern can fit inside the text.

3fill in blank

hard

Fix the error in the code to correctly check for pattern match character by character.

DSA Python

match = True
for j in range(len(pattern)):
    if text[i+j] != [1]:
        match = False
        break

Drag options to blanks, or click blank then click option'

Apattern[j]

Bpattern[i]

Ctext[j]

Dtext[i]

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing text characters with wrong indices.

Using text[i] instead of pattern[j].

We compare each character of the pattern with the corresponding character in the text.

4fill in blank

hard

Fill both blanks to complete the naive pattern matching function.

DSA Python

def naive_pattern_search(text, pattern):
    for i in range(len(text) - [1] + 1):
        match = True
        for j in range([2]):
            if text[i+j] != pattern[j]:
                match = False
                break
        if match:
            print(f"Pattern found at index {i}")

Drag options to blanks, or click blank then click option'

Alen(pattern)

Blen(text)

Attempts:

3 left

💡 Hint

Common Mistakes

Using len(text) in inner loop.

Incorrect loop ranges causing index errors.

The outer loop runs until text length minus pattern length plus one, and inner loop runs over pattern length.

5fill in blank

hard

Fill all three blanks to create a dictionary of pattern occurrences with their start indices.

DSA Python

def find_pattern_positions(text, pattern):
    positions = []
    for i in range(len(text) - [1] + 1):
        if text[i:i+[2]] == [3]:
            positions.append(i)
    return positions

Drag options to blanks, or click blank then click option'

Alen(pattern)

Blen(text)

Cpattern

Dtext

Attempts:

3 left

💡 Hint

Common Mistakes

Using len(text) instead of len(pattern) in loop or slice.

Comparing substring with text instead of pattern.

We use len(pattern) to limit the loop and substring length, and compare with the pattern.

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