Substring Search Patterns in DSA Python

Mental Model

We want to find if a small word or pattern appears inside a bigger text by checking each part carefully.

Analogy: Like looking for a small sticker on a big poster by sliding your eyes over every part until you find a match.

Text: H -> E -> L -> L -> O ->   -> W -> O -> R -> L -> D -> null
Pattern: L -> L -> O -> null
↑ (start of text) ↑ (start of pattern)

Dry Run Walkthrough

Input: text: 'hello world', pattern: 'llo'

Goal: Find the first place where 'llo' appears inside 'hello world'.

Step 1: Check if 'llo' matches starting at 'h' in 'hello world'

h[e][l][l][o] world
pattern: l l o
No match at index 0

Why: We start checking from the first letter to see if pattern fits here

Step 2: Move to next letter 'e' and check again

h e[l][l][o] world
pattern: l l o
No match at index 1

Why: Pattern does not match starting at 'e', so move forward

Step 3: Check starting at 'l' (index 2)

h e [l][l][o] world
pattern: l l o
Match found at index 2

Why: All letters in pattern match the text here

Result:

Final state: 'hello world'
Pattern 'llo' found starting at index 2

Annotated Code

DSA Python

class SubstringSearch:
    def __init__(self, text: str, pattern: str):
        self.text = text
        self.pattern = pattern

    def search(self) -> int:
        n = len(self.text)
        m = len(self.pattern)
        for i in range(n - m + 1):
            match = True
            for j in range(m):
                if self.text[i + j] != self.pattern[j]:
                    match = False
                    break  # mismatch found, stop checking this position
            if match:
                return i  # pattern found at index i
        return -1  # pattern not found


if __name__ == '__main__':
    text = 'hello world'
    pattern = 'llo'
    searcher = SubstringSearch(text, pattern)
    index = searcher.search()
    if index != -1:
        print(f"Pattern '{pattern}' found starting at index {index}")
    else:
        print(f"Pattern '{pattern}' not found in text")

for i in range(n - m + 1):

slide the pattern start position over the text

for j in range(m):

check each character of the pattern against text

if self.text[i + j] != self.pattern[j]:

detect mismatch to stop checking this position early

if match:

return index if full pattern matched

Output

Pattern 'llo' found starting at index 2

Complexity Analysis

Time: O(n*m) because for each of the n positions in text, we check up to m characters of the pattern

Space: O(1) because we only use a few variables, no extra space grows with input size

vs Alternative: Naive search is simple but slow; advanced algorithms like KMP improve to O(n) by avoiding repeated checks

Edge Cases

empty pattern

pattern is found at index 0 by definition

DSA Python

for i in range(n - m + 1):  # handles m=0 by allowing immediate match

pattern longer than text

no match found, returns -1

DSA Python

for i in range(n - m + 1):  # loop does not run if m > n

pattern not in text

returns -1 after checking all positions

DSA Python

return -1  # after all positions checked without match

When to Use This Pattern

When you need to find if a small string appears inside a bigger string, use substring search patterns to check each possible position carefully.

Common Mistakes

Mistake: Not stopping the inner loop early when a mismatch is found, causing unnecessary checks
Fix: Break the inner loop immediately when characters don't match

Mistake: Not handling the case when pattern is empty, which should return 0
Fix: Allow the loop to run even if pattern length is zero, returning 0 immediately

Summary

It finds if and where a smaller string appears inside a bigger string by checking each position.

Use it when you want to locate a word or pattern inside a text.

The key is to slide the pattern over the text and compare characters one by one.

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