String Pattern Matching Naive in DSA Python - Time & Space Complexity

Time Complexity: String Pattern Matching Naive

O(n * m)

Understanding Time Complexity

We want to understand how long it takes to find a pattern inside a text using a simple method.

How does the time needed grow when the text or pattern gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def naive_pattern_search(text: str, pattern: str) -> int:
    n = len(text)
    m = len(pattern)
    for i in range(n - m + 1):
        j = 0
        while j < m and text[i + j] == pattern[j]:
            j += 1
        if j == m:
            return i
    return -1

This code checks every possible place in the text to see if the pattern matches starting there.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Comparing characters of the pattern with the text one by one.
• How many times: For each position in the text (up to n - m + 1), it may compare up to m characters.

How Execution Grows With Input

As the text and pattern get longer, the number of comparisons grows roughly by multiplying their lengths.

Input Size (n)	Approx. Operations
10 (text), 3 (pattern)	About 8 * 3 = 24 comparisons
100 (text), 5 (pattern)	About 96 * 5 = 480 comparisons
1000 (text), 10 (pattern)	About 991 * 10 = 9,910 comparisons

Pattern observation: Doubling the text or pattern length roughly doubles the work, so the total work grows like the product of their sizes.

Final Time Complexity

Time Complexity: O(n * m)

This means the time needed grows proportionally to the length of the text times the length of the pattern.

Common Mistake

[X] Wrong: "The search always takes time proportional to the text length only."

[OK] Correct: Because for each position in the text, the pattern characters are also checked one by one, so pattern length matters too.

Interview Connect

Understanding this simple search helps build intuition for more advanced methods and shows you can analyze nested loops clearly.

Self-Check

"What if we stopped searching after the first mismatch instead of checking all characters? How would the time complexity change?"

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