String Pattern Matching Naive in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Naive Pattern Matching Positions

What is the output of the following code that finds all starting indices where the pattern occurs in the text using naive pattern matching?

DSA Python

def naive_pattern_search(text, pattern):
    positions = []
    n = len(text)
    m = len(pattern)
    for i in range(n - m + 1):
        match = True
        for j in range(m):
            if text[i + j] != pattern[j]:
                match = False
                break
        if match:
            positions.append(i)
    return positions

text = "abracadabra"
pattern = "abra"
print(naive_pattern_search(text, pattern))

A [7]

B [0, 3, 7]

C [3, 7]

D [0, 7]

💡 Hint

Check where the pattern "abra" appears exactly in the text "abracadabra".

The pattern "abra" appears at index 0 and again at index 7 in the text. So the output list contains [0, 7].

❓ Predict Output

intermediate

Output when pattern not found

What is the output of this naive pattern matching code when the pattern does not exist in the text?

DSA Python

def naive_pattern_search(text, pattern):
    positions = []
    n = len(text)
    m = len(pattern)
    for i in range(n - m + 1):
        match = True
        for j in range(m):
            if text[i + j] != pattern[j]:
                match = False
                break
        if match:
            positions.append(i)
    return positions

text = "hello world"
pattern = "bye"
print(naive_pattern_search(text, pattern))

A []

B [0, 6]

C [6]

D [0]

💡 Hint

If the pattern is not found, the list of positions should be empty.

Since "bye" does not appear in "hello world", the function returns an empty list [].

🔧 Debug

advanced

Identify the error in naive pattern matching code

What error does this code raise when run?

DSA Python

def naive_pattern_search(text, pattern):
    positions = []
    n = len(text)
    m = len(pattern)
    for i in range(n - m + 2):
        match = True
        for j in range(m):
            if text[i + j] != pattern[j]:
                match = False
                break
        if match:
            positions.append(i)
    return positions

text = "abcabcabc"
pattern = "abc"
print(naive_pattern_search(text, pattern))

A [0, 3, 6]

B IndexError

C []

D SyntaxError

💡 Hint

Check the loop range for possible off-by-one errors.

The outer loop uses range(n - m + 2), which iterates one too many times (up to i = n - m + 1 = 7). When i=7 and j=2, text[9] causes IndexError.

🧠 Conceptual

advanced

Time complexity of naive pattern matching

What is the worst-case time complexity of the naive pattern matching algorithm for a text of length n and pattern of length m?

A O(n * m)

B O(m^2)

C O(n^2)

D O(n + m)

💡 Hint

Consider how many comparisons are done in the worst case.

The naive algorithm checks each position in the text and compares up to m characters, leading to O(n * m) time complexity.

🚀 Application

expert

Number of matches found by naive pattern matching

Given the text "aaaaaa" and pattern "aaa", how many matches will the naive pattern matching algorithm find?

A 2

B 3

C 4

D 5

💡 Hint

Count all overlapping occurrences of the pattern in the text.

The pattern "aaa" appears starting at indices 0, 1, 2, and 3 in the text "aaaaaa", so 4 matches.

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