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.

Practice

1. What does the in operator check when used like 'abc' in 'abcdef' in Python?

easy

A. If the substring 'abc' exists anywhere inside the string 'abcdef'

B. If the string 'abcdef' starts with 'abc'

C. If the string 'abcdef' ends with 'abc'

D. If the strings 'abc' and 'abcdef' are exactly equal

Solution

1. Step 1: Understand the in operator for strings

   The in operator checks if the left string is found anywhere inside the right string.

2. Step 2: Apply to given strings

   Since 'abc' is at the start of 'abcdef', it is found inside it.

3. Final Answer:

   If the substring 'abc' exists anywhere inside the string 'abcdef' -> Option A

4. Quick Check:

   'abc' in 'abcdef' = True [OK]

Hint: Remember: 'in' checks anywhere inside the string [OK]

Common Mistakes:

• Thinking 'in' only checks start of string
• Confusing 'in' with equality
• Assuming 'in' checks only end of string

2. Which of the following is the correct syntax to find the index of substring 'cat' in string s = 'concatenate' using Python?

easy

A. s.indexOf('cat')

B. find(s, 'cat')

C. s.find('cat')

D. index(s, 'cat')

Solution

1. Step 1: Recall Python string method for substring index

   Python strings have a method called find() to locate substring index.

2. Step 2: Check method usage

   The correct syntax is s.find('cat'). Other options are invalid in Python.

3. Final Answer:

   s.find('cat') -> Option C

4. Quick Check:

   Use string.find(substring) syntax [OK]

Hint: Use string.find(substring) to get index [OK]

Common Mistakes:

• Using non-Python syntax like indexOf
• Calling find as a standalone function
• Confusing method name or order of arguments

3. What will be the output of the following code?

text = 'abracadabra'
pos = text.find('ra')
print(pos)

medium

A. 2

B. 1

C. 3

D. -1

Solution

1. Step 1: Understand find() method behavior

   The find() method returns the lowest index where the substring is found or -1 if not found.

2. Step 2: Locate substring 'ra' in 'abracadabra'

   The substring 'ra' first appears starting at index 1 (abracadabra).

3. Final Answer:

   1 -> Option B

4. Quick Check:

   First 'ra' at index 1 [OK]

Hint: Remember: find() returns first occurrence index [OK]

Common Mistakes:

• Assuming find() returns all occurrences
• Confusing index with count
• Mistaking find() return -1 for found substring

4. Identify the error in the following code snippet that tries to check if substring 'dog' is in string s:

s = 'hotdog'
if s.contains('dog'):
    print('Found')
else:
    print('Not Found')

medium

A. The method contains does not exist for strings in Python

B. The substring 'dog' is misspelled

C. The string s is not defined

D. The print statements are incorrect

Solution

1. Step 1: Check string method availability in Python

   Python strings do not have a contains() method; membership is checked with in.

2. Step 2: Correct way to check substring presence

   Use 'dog' in s instead of s.contains('dog').

3. Final Answer:

   The method contains does not exist for strings in Python -> Option A

4. Quick Check:

   Use in operator, not contains() [OK]

Hint: Use in for substring check, not contains() [OK]

Common Mistakes:

• Using Java-like contains() method in Python
• Misspelling substring or variable
• Assuming print syntax is wrong

5. Given a string s = 'banana', which code snippet correctly finds all starting indices of substring 'ana' in s?

hard

A. indices = [s.find('ana')]

B. indices = [i for i in range(len(s)) if 'ana' in s[i]]

C. indices = [i for i in range(len(s)) if s.find('ana') == i]

D. indices = [i for i in range(len(s)) if s[i:i+3] == 'ana']

Solution

1. Step 1: Understand substring search for all occurrences

   To find all starting indices, check each position if substring matches.

2. Step 2: Analyze each option

   indices = [i for i in range(len(s)) if s[i:i+3] == 'ana'] uses slicing and compares substring at each index correctly. indices = [s.find('ana')] finds only first occurrence. indices = [i for i in range(len(s)) if s.find('ana') == i] incorrectly compares find() result to index. indices = [i for i in range(len(s)) if 'ana' in s[i]] incorrectly checks membership of substring in single character.

3. Final Answer:

   indices = [i for i in range(len(s)) if s[i:i+3] == 'ana'] -> Option D

4. Quick Check:

   Slice and compare at each index for all matches [OK]

Hint: Use slicing and loop to find all substring start indices [OK]

Common Mistakes:

• Using find() only returns first match
• Comparing find() result incorrectly
• Checking substring in single character