String Pattern Matching Naive in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Naive Pattern Matching with Single Match

What is the output of this Go code that uses naive string pattern matching to find the first occurrence of a pattern in a text?

DSA Go

package main
import "fmt"
func naivePatternMatch(text, pattern string) int {
    n := len(text)
    m := len(pattern)
    for i := 0; i <= n-m; i++ {
        j := 0
        for j < m && text[i+j] == pattern[j] {
            j++
        }
        if j == m {
            return i
        }
    }
    return -1
}
func main() {
    text := "abracadabra"
    pattern := "cada"
    fmt.Println(naivePatternMatch(text, pattern))
}

A 5

B 3

C -1

D 4

💡 Hint

Check where the pattern "cada" starts in the text "abracadabra".

The pattern "cada" starts at index 4 in the text "abracadabra". The naive algorithm checks each position until it finds a full match.

❓ Predict Output

intermediate

Output when Pattern Not Found

What does the naive pattern matching function return when the pattern is not found in the text?

DSA Go

package main
import "fmt"
func naivePatternMatch(text, pattern string) int {
    n := len(text)
    m := len(pattern)
    for i := 0; i <= n-m; i++ {
        j := 0
        for j < m && text[i+j] == pattern[j] {
            j++
        }
        if j == m {
            return i
        }
    }
    return -1
}
func main() {
    text := "hello world"
    pattern := "bye"
    fmt.Println(naivePatternMatch(text, pattern))
}

A -1

B 0

C 11

D 5

💡 Hint

If the pattern is not found, what index does the function return?

The function returns -1 to indicate the pattern was not found in the text.

🧠 Conceptual

advanced

Time Complexity of Naive Pattern Matching

What is the worst-case time complexity of the naive string pattern matching algorithm when searching for a pattern of length m in a text of length n?

A O(n * m)

B O(n + m)

C O(n^2)

D O(m^2)

💡 Hint

Consider how many comparisons are done in the worst case for each position in the text.

The naive algorithm checks each position in the text and compares up to m characters, leading to O(n * m) complexity.

🔧 Debug

advanced

Identify the Bug in Naive Pattern Matching Code

Which option contains a bug that causes incorrect pattern matching results?

DSA Go

func naivePatternMatch(text, pattern string) int {
    n := len(text)
    m := len(pattern)
    for i := 0; i < n-m; i++ {
        j := 0
        for j < m && text[i+j] == pattern[j] {
            j++
        }
        if j == m {
            return i
        }
    }
    return -1
}

A The inner loop should use '||' instead of '&&' in the condition

B The loop condition should be i <= n-m, not i < n-m

C The function should return i+1 instead of i when a match is found

D The function should return -2 when no match is found

💡 Hint

Check the loop boundary to ensure the pattern can fit at the last possible position.

The outer loop must run until i <= n-m to check the last valid position where the pattern can fit.

🚀 Application

expert

Number of Matches Found by Naive Pattern Matching

Given the text "aaaaa" and the pattern "aa", how many matches will the naive pattern matching algorithm find if modified to find all occurrences?

DSA Go

package main
import "fmt"
func naivePatternMatchAll(text, pattern string) []int {
    n := len(text)
    m := len(pattern)
    var matches []int
    for i := 0; i <= n-m; i++ {
        j := 0
        for j < m && text[i+j] == pattern[j] {
            j++
        }
        if j == m {
            matches = append(matches, i)
        }
    }
    return matches
}
func main() {
    text := "aaaaa"
    pattern := "aa"
    fmt.Println(naivePatternMatchAll(text, pattern))
}

A 5

B 3

C 4

D 2

💡 Hint

Count overlapping occurrences of "aa" in "aaaaa".

The pattern "aa" appears starting at indices 0,1,2,3 in the text "aaaaa", totaling 4 matches.

Practice

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

easy

A. Check every possible position in the text for the pattern

B. Use a hash function to find the pattern quickly

C. Preprocess the pattern to skip some comparisons

D. Sort the text and pattern before matching

Solution

1. Step 1: Understand naive matching approach

   The naive algorithm tries to match the pattern starting at each position in the text one by one.

2. Step 2: Compare with other methods

   Other methods like hashing or preprocessing are not part of the naive approach.

3. Final Answer:

   Check every possible position in the text for the pattern -> Option A

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 preprocessing is done
• Believing text is sorted first

2. Which of the following Go code snippets correctly starts the outer loop for naive string pattern matching?

easy

A. for i := 0; i <= len(text)-len(pattern); i++ {

B. for i := 0; i < len(text); i++ {

C. for i := 1; i <= len(text); i++ {

D. for i := 0; i < len(pattern); i++ {

Solution

1. Step 1: Determine loop range for matching

   The outer loop must run from 0 to len(text)-len(pattern) to avoid out-of-range errors.

2. Step 2: Check each option

   for i := 0; i <= len(text)-len(pattern); i++ { correctly uses i <= len(text)-len(pattern). Others either go too far or use wrong limits.

3. Final Answer:

   for i := 0; i <= len(text)-len(pattern); i++ { -> Option A

4. Quick Check:

   Loop till text length minus pattern length [OK]

Hint: Loop till text length minus pattern length [OK]

Common Mistakes:

• Looping beyond valid start positions
• Starting loop from 1 instead of 0
• Using pattern length as loop limit

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

text := "banana"
pattern := "ana"
count := 0
for i := 0; i <= len(text)-len(pattern); i++ {
  j := 0
  for j < len(pattern) && text[i+j] == pattern[j] {
    j++
  }
  if j == len(pattern) {
    count++
  }
}
fmt.Println(count)

medium

A. 1

B. 3

C. 0

D. 2

Solution

1. Step 1: Identify pattern matches in text

   Check each position in "banana" for "ana": positions 1-3 and 3-5 match.

2. Step 2: Count matches

   Two matches found, so count is 2.

3. Final Answer:

   2 -> Option D

4. Quick Check:

   "ana" appears twice in "banana" [OK]

Hint: Count all exact matches sliding over text [OK]

Common Mistakes:

• Counting overlapping matches incorrectly
• Off-by-one errors in loop limits
• Assuming only first match counts

4. The following Go code tries to count pattern occurrences but has a bug. What is the bug?

text := "abcabcabc"
pattern := "abc"
count := 0
for i := 0; i < len(text)-len(pattern); i++ {
  j := 0
  for j < len(pattern) && text[i+j] == pattern[j] {
    j++
  }
  if j == len(pattern) {
    count++
  }
}
fmt.Println(count)

medium

A. The inner loop condition is wrong

B. The outer loop should use <= instead of <

C. The count variable is not initialized

D. The pattern length is not checked

Solution

1. Step 1: Analyze outer loop range

   The loop runs from 0 to len(text)-len(pattern)-1, missing last valid start index.

2. Step 2: Correct loop condition

   Changing < to <= includes last position, fixing missed matches.

3. Final Answer:

   The outer loop should use <= instead of < -> Option B

4. Quick Check:

   Loop must cover last valid start index [OK]

Hint: Use <= to include last possible start index [OK]

Common Mistakes:

• Using < instead of <= in outer loop
• Ignoring last possible match position
• Misunderstanding loop boundaries

5. Given the text "abracadabra" and pattern "abra", how many times will the naive algorithm find the pattern if overlapping matches are counted? Use the naive approach code below:

text := "abracadabra"
pattern := "abra"
count := 0
for i := 0; i <= len(text)-len(pattern); i++ {
  j := 0
  for j < len(pattern) && text[i+j] == pattern[j] {
    j++
  }
  if j == len(pattern) {
    count++
  }
}
fmt.Println(count)

hard

A. 3

B. 1

C. 2

D. 4

Solution

1. Step 1: Identify all pattern matches including overlaps

   "abra" appears at positions 0-3 and 7-10 in "abracadabra".

2. Step 2: Count total matches

   Two matches found, so count is 2.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   "abra" occurs twice overlapping allowed [OK]

Hint: Check all positions including overlaps [OK]

Common Mistakes:

• Counting only first match
• Missing second overlapping match
• Confusing substring positions