String Pattern Matching Naive in DSA Go

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 checking if it fits perfectly.

Text:  T  E  X  T  T  E  X  T  
Index: [0][1][2][3][4][5][6][7]
Pattern: P  A  T  T  E  R  N
Try matching pattern starting at each text index.

Dry Run Walkthrough

Input: text: "ABABABC", pattern: "ABABC"

Goal: Find the first index where the pattern "ABABC" appears in the 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]
Compare text[0..4] with pattern[0..4]

Why: We start checking from the beginning of the text to find a match

Step 2: Compare characters one by one: text[0]=A vs pattern[0]=A (match), text[1]=B vs pattern[1]=B (match), text[2]=A vs pattern[2]=A (match), text[3]=B vs pattern[3]=B (match), text[4]=A vs pattern[4]=C (mismatch)

Mismatch at text index 4 and pattern index 4

Why: Mismatch means pattern does not match starting at index 0

Step 3: Check pattern starting at text index 1

Text: A [B][A][B][A][B][C]
Pattern: [A][B][A][B][C]
Compare text[1..5] with pattern[0..4]

Why: Try next position in text to find pattern

Step 4: Compare characters one by one: text[1]=B vs pattern[0]=A (mismatch)

Mismatch at text index 1 and pattern index 0

Why: Mismatch means pattern does not match starting at index 1

Step 5: Check pattern starting at text index 2

Text: A B [A][B][A][B][C]
Pattern: [A][B][A][B][C]
Compare text[2..6] with pattern[0..4]

Why: Try next position in text to find pattern

Step 6: Compare characters one by one: text[2]=A vs pattern[0]=A (match), text[3]=B vs pattern[1]=B (match), text[4]=A vs pattern[2]=A (match), text[5]=B vs pattern[3]=B (match), text[6]=C vs pattern[4]=C (match)

Full match found at text index 2

Why: All characters matched, pattern found

Result:

Pattern found at index 2

Annotated Code

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++ // advance j while characters match
        }
        if j == m {
            return i // full pattern matched at index i
        }
    }
    return -1 // pattern not found
}

func main() {
    text := "ABABABC"
    pattern := "ABABC"
    index := naivePatternMatch(text, pattern)
    if index != -1 {
        fmt.Printf("Pattern found at index %d\n", index)
    } else {
        fmt.Println("Pattern not found")
    }
}

for i := 0; i <= n-m; i++ {

Try matching pattern starting at each possible text index

for j < m && text[i+j] == pattern[j] {

Compare characters one by one until mismatch or full match

if j == m {

If full pattern matched, return current index

Output

Pattern found at index 2

Complexity Analysis

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

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

vs Alternative: More efficient algorithms like KMP run in O(n+m) time by avoiding repeated comparisons

Edge Cases

Empty pattern

Returns 0 immediately since empty pattern matches at start

DSA Go

for i := 0; i <= n-m; i++ {

Pattern longer than text

Returns -1 immediately since pattern cannot fit

DSA Go

for i := 0; i <= n-m; i++ {

Pattern not in text

Returns -1 after checking all positions

DSA Go

return -1 // pattern not found

When to Use This Pattern

When you need to find if a small string appears inside a bigger string and no advanced preprocessing is required, use naive pattern matching to check every possible position.

Common Mistakes

Mistake: Not stopping the inner loop on mismatch and continuing to compare characters
Fix: Break the inner loop immediately when a mismatch is found

Mistake: Checking beyond the text length causing index out of range
Fix: Limit outer loop to n-m to avoid overflow

Summary

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

Use when pattern matching is simple and input sizes are small or when learning the basics.

The key insight is sliding the pattern over the text and stopping early on mismatches to avoid unnecessary checks.

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