String Pattern Matching Naive in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

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

It checks for the pattern at every possible position in the text by comparing characters one by one until a match is found or all positions are checked.

intermediate

What is the worst-case time complexity of the naive string pattern matching algorithm?

O(m * n), where m is the length of the pattern and n is the length of the text, because it may check every character of the text for each character of the pattern.

beginner

In the naive pattern matching, what happens when a mismatch occurs during comparison?

The algorithm shifts the pattern by one position to the right in the text and starts comparing again from the first character of the pattern.

intermediate

Why is the naive string pattern matching algorithm not efficient for large texts and patterns?

Because it may repeatedly compare the same characters many times, leading to a high number of comparisons especially when the pattern and text have many repeated characters.

beginner

Show the output of naive pattern matching for text = 'abcabcabc' and pattern = 'abc'.

The pattern 'abc' is found at positions 0, 3, and 6 in the text.

What does the naive string pattern matching algorithm do when it finds a mismatch?

A Stops searching immediately

B Skips multiple characters based on mismatch

C Shifts the pattern by one position and restarts comparison

D Reverses the pattern

The naive algorithm shifts the pattern by one position to the right and starts comparing again from the first character.

What is the best case time complexity of the naive string pattern matching algorithm?

A O(m + n)

B O(n)

C O(m * n)

D O(m)

In the best case, the pattern matches immediately or mismatches early, so it takes O(n) time scanning the text once.

Which of the following is true about the naive string pattern matching algorithm?

A It compares characters one by one without preprocessing

B It uses preprocessing of the pattern

C It uses a hash function to speed up matching

D It only works for numeric patterns

The naive algorithm compares characters one by one without any preprocessing or hashing.

If the text length is 10 and pattern length is 3, how many maximum comparisons can naive pattern matching make?

A 10

B 3

C 13

D 24

Maximum comparisons = (n - m + 1) * m = (10 - 3 + 1) * 3 = 8 * 3 = 24.

Which scenario causes the naive algorithm to perform the most comparisons?

A Pattern and text have many repeated characters causing partial matches

B Pattern and text have no common characters

C Pattern is very short

D Pattern is longer than text

Repeated characters causing partial matches lead to many repeated comparisons, increasing the total comparisons.

Explain how the naive string pattern matching algorithm works step-by-step.

Think about sliding the pattern over the text and checking each character.

Describe the advantages and disadvantages of the naive string pattern matching algorithm.

Consider ease of use versus performance.

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