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.