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.

Practice

1. What is the main idea behind the naive string pattern matching algorithm?

easy

A. Sort the text and pattern before matching

B. Use a hash function to find the pattern quickly

C. Preprocess the pattern to skip some comparisons

D. Check every possible position in the text to see if the pattern matches

Solution

1. Step 1: Understand naive matching approach

   The naive algorithm tries to match the pattern starting at every position in the text.

2. Step 2: Compare with other methods

   Other methods use hashing or preprocessing, but naive does not.

3. Final Answer:

   Check every possible position in the text to see if the pattern matches -> Option D

4. Quick Check:

   Naive = Check all positions [OK]

Hint: Naive means try all positions one by one [OK]

Common Mistakes:

• Thinking naive uses hashing
• Assuming pattern is preprocessed
• Believing text is sorted before matching

2. Which of the following is the correct syntax to start checking pattern matching at index i in text using naive approach in Python?

easy

A. for j in range(len(pattern)): if text[i+j] != pattern[j]: break

B. for j in range(len(text)): if pattern[i+j] != text[j]: break

C. for i in range(len(pattern)): if text[j+i] != pattern[j]: break

D. for j in range(len(pattern)): if pattern[j] != text[j]: break

Solution

1. Step 1: Identify correct loop variables and indexing

   We loop over pattern length with j, compare text[i+j] with pattern[j].

2. Step 2: Check each option's indexing

   for j in range(len(pattern)): if text[i+j] != pattern[j]: break correctly uses text[i+j] and pattern[j]. Others mix indices or variables incorrectly.

3. Final Answer:

   for j in range(len(pattern)): if text[i+j] != pattern[j]: break -> Option A

4. Quick Check:

   Correct indexing = for j in range(len(pattern)): if text[i+j] != pattern[j]: break [OK]

Hint: Pattern index j matches text at i+j [OK]

Common Mistakes:

• Swapping text and pattern indices
• Using wrong loop variable
• Mixing i and j incorrectly

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

text = "abracadabra"
pattern = "cada"
positions = []
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:
        positions.append(i)
print(positions)

medium

A. [5]

B. [3]

C. [4]

D. []

Solution

1. Step 1: Check substring positions in text

   Pattern 'cada' length is 4. Check text from index 0 to 7 (11-4).

2. Step 2: Find matching index

   At index 4: text[4:8] = 'cada' matches pattern exactly.

3. Final Answer:

   [4] -> Option C

4. Quick Check:

   Match at index 4 only [OK]

Hint: Check substring slices matching pattern length [OK]

Common Mistakes:

• Off-by-one error in range
• Misreading substring indices
• Appending wrong index on match

4. The following code is intended to find all occurrences of a pattern in a text using naive matching. What is the bug?

text = "hellohello"
pattern = "llo"
positions = []
for i in range(len(text) - len(pattern)):
    match = True
    for j in range(len(pattern)):
        if text[i+j] != pattern[j]:
            match = False
            break
    if match:
        positions.append(i)
print(positions)

medium

A. The inner loop uses wrong indices for pattern

B. The range in outer loop misses last possible position

C. The match flag is reset incorrectly

D. Positions list is not initialized

Solution

1. Step 1: Analyze outer loop range

   Outer loop uses range(len(text) - len(pattern)) which excludes last valid start index.

2. Step 2: Correct range to include last position

   It should be range(len(text) - len(pattern) + 1) to check all positions.

3. Final Answer:

   The range in outer loop misses last possible position -> Option B

4. Quick Check:

   Loop range off by one [OK]

Hint: Outer loop must cover all start indices [OK]

Common Mistakes:

• Using range without +1
• Confusing inner loop indices
• Not resetting match flag properly

5. Given a text and a pattern, how can you modify the naive string pattern matching algorithm to count overlapping occurrences of the pattern in the text? For example, in text = "aaaaa" and pattern = "aaa", the count should be 3.

hard

A. After finding a match at index i, continue checking from i+1 instead of i+len(pattern)

B. Skip checking overlapping indices by moving i by len(pattern) after a match

C. Use a hash function to detect overlaps

D. Reverse the text and pattern before matching

Solution

1. Step 1: Understand overlapping matches

   Overlapping means matches can start before previous match ends.

2. Step 2: Modify iteration after match

   Instead of skipping ahead by pattern length, move only one step forward to catch overlaps.

3. Final Answer:

   After finding a match at index i, continue checking from i+1 instead of i+len(pattern) -> Option A

4. Quick Check:

   Move one step after match for overlaps [OK]

Hint: Move one step after match to count overlaps [OK]

Common Mistakes:

• Skipping too far after match
• Using hashing unnecessarily
• Reversing strings without reason