String Pattern Matching Naive in DSA Python

Mental Model

Check every possible place in the text to see if the pattern matches exactly.

Analogy: Like looking for a small picture in a big photo by sliding it over every spot and comparing pixel by pixel.

Text:  T  E  X  T  
Index: [0][1][2][3]
Pattern: P  A  T
Index: [0][1][2]

We try to match pattern starting at each text index.

Dry Run Walkthrough

Input: text: 'ABABABC', pattern: 'ABABC'

Goal: Find the starting index where pattern 'ABABC' appears in text 'ABABABC'.

Step 1: Check pattern starting at text index 0

Text: [A][B][A][B][A][B][C]
       ↑
Pattern: [A][B][A][B][C]
         ↑

Why: We start matching pattern from the first character of text.

Step 2: Compare characters one by one at text indices 0 to 4

Match at indices 0:A=A, 1:B=B, 2:A=A, 3:B=B, 4:A≠C (mismatch)
Text: [A][B][A][B][A][B][C]
       ↑
Pattern: [A][B][A][B][C]
         ↑

Why: Mismatch at pattern index 4 means pattern does not match here.

Step 3: Move pattern start to text index 1

Text: [A][B][A][B][A][B][C]
          ↑
Pattern: [A][B][A][B][C]
            ↑

Why: Try matching pattern starting from next character in text.

Step 4: Compare characters at text indices 1 to 5

Match at indices 1:B≠A (mismatch at first char)
Text: [A][B][A][B][A][B][C]
          ↑
Pattern: [A][B][A][B][C]
            ↑

Why: Mismatch at first character means no match here.

Step 5: Move pattern start to text index 2

Text: [A][B][A][B][A][B][C]
             ↑
Pattern: [A][B][A][B][C]
               ↑

Why: Try matching pattern starting from next character in text.

Step 6: Compare characters one by one at text indices 2 to 6

Match at indices 2:A=A, 3:B=B, 4:A=A, 5:B=B, 6:C=C
Full match found
Text: [A][B][A][B][A][B][C]
             ↑
Pattern: [A][B][A][B][C]
               ↑

Why: All characters match, pattern found starting at index 2.

Result:

Pattern found at index 2

Annotated Code

DSA Python

class NaivePatternMatcher:
    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):  # slide pattern over text
            match = True
            for j in range(m):  # check each character
                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 = 'ABABABC'
    pattern = 'ABABC'
    matcher = NaivePatternMatcher(text, pattern)
    index = matcher.search()
    if index != -1:
        print(f'Pattern found at index {index}')
    else:
        print('Pattern not found')

for i in range(n - m + 1): # slide pattern over text

slide pattern start index over text to check all possible positions

for j in range(m): # check each character

compare pattern characters one by one with text characters

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

detect mismatch to stop checking current position early

if match: return i # pattern found at index i

return index immediately when full pattern matches

Output

Pattern found at index 2

Complexity Analysis

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

Space: O(1) because no extra space proportional to input size is used

vs Alternative: Compared to advanced algorithms like KMP which run in O(n+m), naive is slower but simpler to implement

Edge Cases

Empty pattern

Returns 0 immediately since empty pattern matches at start

DSA Python

for i in range(n - m + 1):  # slide pattern over text

Pattern longer than text

Loop does not run, returns -1 meaning no match

DSA Python

for i in range(n - m + 1):  # slide pattern over text

Pattern equals text

Matches at index 0 if all characters equal

DSA Python

if match:
    return i  # pattern found at index i

When to Use This Pattern

When asked to find if a small string appears inside a bigger string and no advanced preprocessing is required, try the naive pattern matching by checking all positions.

Common Mistakes

Mistake: Not stopping inner loop on mismatch, causing unnecessary comparisons
Fix: Add break statement immediately when mismatch is found

Mistake: Looping beyond valid start indices causing index errors
Fix: Use range(n - m + 1) to ensure pattern fits inside text

Summary

It checks every possible position in the text to find the pattern by comparing characters one by one.

Use it when you want a simple solution for pattern searching without preprocessing.

The key insight is sliding the pattern over the text and stopping early on mismatches to save work.