Substring Search Patterns in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of naive substring search count

What is the output of the following code that counts occurrences of a pattern in a text using a naive approach?

DSA Python

def naive_search(text, pattern):
    count = 0
    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:
            count += 1
    return count

print(naive_search('abababa', 'aba'))

A 2

B 3

C 4

D 1

💡 Hint

Check all possible starting positions where 'aba' can appear in 'abababa'.

The pattern 'aba' appears starting at indices 0, 2, and 4 in the text 'abababa'. So, the count is 3.

🧠 Conceptual

intermediate

Understanding the prefix function in KMP algorithm

What does the prefix function (also called the failure function) in the Knuth-Morris-Pratt (KMP) substring search algorithm represent?

A The length of the longest proper prefix of the pattern that is also a suffix for each prefix of the pattern

B The number of times the pattern appears in the text

C The index where the pattern first appears in the text

D The length of the pattern

💡 Hint

Think about what helps KMP avoid rechecking characters after a mismatch.

The prefix function stores for each position in the pattern the length of the longest prefix that matches a suffix ending at that position. This helps KMP skip unnecessary comparisons.

❓ Predict Output

advanced

Output of Rabin-Karp hash matches

What is the output of this Rabin-Karp substring search code that prints all starting indices where the pattern matches the text?

DSA Python

def rabin_karp(text, pattern):
    d = 256
    q = 101
    n = len(text)
    m = len(pattern)
    h = pow(d, m-1, q)
    p = 0
    t = 0
    result = []

    for i in range(m):
        p = (d * p + ord(pattern[i])) % q
        t = (d * t + ord(text[i])) % q

    for i in range(n - m + 1):
        if p == t:
            if text[i:i+m] == pattern:
                result.append(i)
        if i < n - m:
            t = (d * (t - ord(text[i]) * h) + ord(text[i + m])) % q
            if t < 0:
                t += q
    return result

print(rabin_karp('abracadabra', 'abra'))

A [1, 7]

B [0, 3]

C [3, 7]

D [0, 7]

💡 Hint

Check where 'abra' appears in 'abracadabra'.

The pattern 'abra' appears at index 0 and index 7 in the text 'abracadabra'. The Rabin-Karp algorithm finds these indices.

🔧 Debug

advanced

Identify the error in this KMP prefix function code

What error does this prefix function code for KMP produce when run?

DSA Python

def prefix_function(pattern):
    pi = [0] * len(pattern)
    k = 0
    for q in range(1, len(pattern)):
        while k > 0 and pattern[k] != pattern[q]:
            k = pi[k-1]
        if pattern[k] == pattern[q]:
            k += 1
        pi[q] = k
    return pi

print(prefix_function('ababc'))

A IndexError: list index out of range

B [0, 0, 1, 2, 0]

C [0, 0, 1, 2, 1]

D TypeError: unsupported operand type(s)

💡 Hint

Check the line where k is updated inside the while loop.

The code uses pi[k] but k can be equal to len(pattern), causing an IndexError.

🚀 Application

expert

Minimum window substring containing all pattern characters

Given a text and a pattern, which algorithmic approach efficiently finds the smallest substring in the text that contains all characters of the pattern (including duplicates)?

A KMP algorithm for exact pattern matching

B Naive substring search checking all substrings

C Sliding window with two pointers and a frequency map

D Rabin-Karp algorithm with rolling hash

💡 Hint

Think about how to track counts of characters while expanding and shrinking a window.

The sliding window approach with two pointers and a frequency map efficiently finds the minimum window containing all pattern characters by expanding and contracting the window.