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.