String Pattern Matching Naive in DSA Go - Build from Scratch

String Pattern Matching Naive

📖 Scenario: You are building a simple search tool that finds where a small word (pattern) appears inside a bigger text (string). This is like looking for a word in a book page.

🎯 Goal: Build a program that checks every position in the text to see if the pattern starts there, and prints all the starting positions where the pattern is found.

📋 What You'll Learn

Create a string variable text with the exact value "abracadabra"

Create a string variable pattern with the exact value "abra"

Use a for loop with variable i to check each possible starting position in text

Use a nested for loop with variable j to compare characters of pattern with text

Print all starting indices where pattern matches text

💡 Why This Matters

🌍 Real World

Searching for words or phrases inside documents, like finding keywords in emails or text files.

💼 Career

Understanding basic string search algorithms is important for roles in software development, data processing, and text analysis.

1

Create the text string

Create a string variable called text and set it to the exact value "abracadabra"

DSA Go

// Create the string variable text with value "abracadabra"
// Your code here

Hint

Use text := "abracadabra" to create the string.

2

Create the pattern string

Add a string variable called pattern and set it to the exact value "abra"

DSA Go

package main

func main() {
    text := "abracadabra"
    // Create the string variable pattern with value "abra"
    // Your code here
}

Hint

Use pattern := "abra" to create the pattern string.

3

Implement the naive pattern matching loops

Use a for loop with variable i from 0 to len(text) - len(pattern) inclusive to check each possible start position. Inside it, use a nested for loop with variable j from 0 to len(pattern) to compare characters of pattern with text. If all characters match, append i to a slice called positions.

DSA Go

package main

func main() {
    text := "abracadabra"
    pattern := "abra"
    positions := []int{}
    // Use a for loop with i to check each start position
    // Use a nested for loop with j to compare characters
    // If all match, append i to positions
    // Your code here
}

Hint

Use two loops: outer with i for start positions, inner with j for character checks. Use a boolean match to track if all characters match.

4

Print the matching positions

Print the slice positions using fmt.Println(positions) to show all starting indices where the pattern matches the text.

DSA Go

package main

import "fmt"

func main() {
    text := "abracadabra"
    pattern := "abra"
    positions := []int{}

    for i := 0; i <= len(text)-len(pattern); i++ {
        match := true
        for j := 0; j < len(pattern); j++ {
            if text[i+j] != pattern[j] {
                match = false
                break
            }
        }
        if match {
            positions = append(positions, i)
        }
    }

    // Print the positions slice
    // Your code here
}

Hint

Use fmt.Println(positions) to print the slice of matching indices.

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