Substring Search Patterns in DSA Go

Mental Model

Find if a smaller word appears inside a bigger word by checking each position step by step.

Analogy: Like looking for a small sticker on a long ribbon by sliding your eyes along the ribbon until you find a match.

Text: H E L L O W O R L D
Pattern:   L L O
           ↑

Dry Run Walkthrough

Input: text: HELLOWORLD, pattern: LLO

Goal: Find the starting position where 'LLO' appears in 'HELLOWORLD'.

Step 1: Check substring starting at index 0: HEL

H E L L O W O R L D
↑ pattern start at 0

Why: Start checking from the beginning of the text.

Step 2: Compare 'HEL' with 'LLO' - no match, move to next index

H E L L O W O R L D
  ↑ pattern start at 1

Why: No match, so slide pattern one step forward.

Step 3: Check substring starting at index 1: ELL

H E L L O W O R L D
  ↑ pattern start at 1

Why: Continue sliding pattern along text.

Step 4: Compare 'ELL' with 'LLO' - no match, move to next index

H E L L O W O R L D
    ↑ pattern start at 2

Why: No match, slide pattern forward.

Step 5: Check substring starting at index 2: LLO

H E L L O W O R L D
    ↑ pattern start at 2

Why: Check substring that might match pattern.

Step 6: Compare 'LLO' with 'LLO' - match found

H E L L O W O R L D
    ↑ pattern start at 2

Why: Pattern matches substring starting at index 2.

Result:

H E L L O W O R L D
    ↑ pattern start at 2
Answer: Pattern found at index 2

Annotated Code

DSA Go

package main

import (
	"fmt"
)

func substringSearch(text, pattern string) int {
	textLen := len(text)
	patternLen := len(pattern)

	for i := 0; i <= textLen-patternLen; i++ {
		match := true
		for j := 0; j < patternLen; j++ {
			if text[i+j] != pattern[j] {
				match = false
				break
			}
		}
		if match {
			return i
		}
	}
	return -1
}

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

for i := 0; i <= textLen-patternLen; i++ {

slide pattern start index along text

for j := 0; j < patternLen; j++ {

compare each character of pattern with text substring

if text[i+j] != pattern[j] { match = false; break }

stop checking if any character does not match

if match { return i }

return index if full pattern matched

Output

Pattern found at index 2

Complexity Analysis

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

Space: O(1) because no extra space is used except variables

vs Alternative: Naive search is simple but slow; advanced algorithms like KMP improve to O(n) by avoiding repeated comparisons

Edge Cases

Empty pattern

Returns 0 because empty pattern matches at start

DSA Go

for i := 0; i <= textLen-patternLen; i++ {

Pattern longer than text

Returns -1 immediately because no match possible

DSA Go

for i := 0; i <= textLen-patternLen; i++ {

Pattern not found in text

Returns -1 after checking all positions

DSA Go

return -1

When to Use This Pattern

When asked to find if a small string appears inside a bigger string, try sliding the small string along the big one and compare characters step by step.

Common Mistakes

Mistake: Not stopping inner loop when characters don't match, causing unnecessary checks
Fix: Break inner loop immediately when a mismatch is found

Mistake: Checking beyond text length causing index out of range error
Fix: Limit outer loop to text length minus pattern length

Summary

Finds the first position where a smaller string appears inside a bigger string by checking each possible start.

Use when you need to locate a substring inside a larger string without advanced preprocessing.

Slide the pattern along the text and compare characters one by one until a match is found or all positions are checked.

Practice

1. What does the strings.Contains(s, substr) function in Go do?

easy

A. Returns the index of substr in s

B. Checks if substr is present anywhere in s

C. Splits s by substr

D. Replaces substr with another string in s

Solution

1. Step 1: Understand the function purpose

   strings.Contains checks if one string is inside another.

2. Step 2: Check the return type

   It returns true if substr is found anywhere in s, otherwise false.

3. Final Answer:

   Checks if substr is present anywhere in s -> Option B

4. Quick Check:

   Contains means presence check = A [OK]

Hint: Contains means checking presence, not position or replacement [OK]

Common Mistakes:

• Confusing Contains with Index or Replace functions
• Thinking it returns position instead of boolean
• Assuming it modifies the original string

2. Which of the following is the correct syntax to find the index of substring "go" in string s using Go's standard library?

easy

A. index := strings.Index(s, "go")

B. index := s.IndexOf("go")

C. index := s.find("go")

D. index := strings.Find(s, "go")

Solution

1. Step 1: Recall Go's strings package functions

   The correct function to find substring index is strings.Index.

2. Step 2: Check syntax correctness

   The function is called as strings.Index(s, "go"), returning the first index or -1 if not found.

3. Final Answer:

   index := strings.Index(s, "go") -> Option A

4. Quick Check:

   Index function in strings package = B [OK]

Hint: Use strings.Index for substring position in Go [OK]

Common Mistakes:

• Using methods on string variable directly (strings are not objects)
• Using Python or JavaScript syntax like find or IndexOf
• Calling non-existent functions like strings.Find

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

package main
import (
  "fmt"
  "strings"
)
func main() {
  s := "hello golang"
  pos := strings.Index(s, "go")
  fmt.Println(pos)
}

medium

A. 6

B. -1

C. 0

D. Error

Solution

1. Step 1: Understand strings.Index behavior

   It returns the first index where substring "go" appears in "hello golang".

2. Step 2: Find substring position

   Counting from 0: h(0) e(1) l(2) l(3) o(4) ' '(5) g(6) o(7)... So "go" starts at index 6.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Index of "go" in "hello golang" = 6 [OK]

Hint: Count characters from zero to find substring index [OK]

Common Mistakes:

• Counting from 1 instead of 0
• Assuming substring not found returns 0
• Confusing Index with Contains boolean

4. Identify the error in the following Go code snippet for substring search:

package main
import (
  "fmt"
  "strings"
)
func main() {
  s := "golang"
  if s.Contains("go") {
    fmt.Println("Found")
  }
}

medium

A. Incorrect string literal syntax

B. Missing import for fmt package

C. No error, code runs fine

D. strings package has no Contains method on string variable

Solution

1. Step 1: Check method call on string variable

   In Go, strings are not objects and do not have methods like Contains directly.

2. Step 2: Correct usage of Contains function

   The correct call is strings.Contains(s, "go") from the strings package, not s.Contains("go").

3. Final Answer:

   strings package has no Contains method on string variable -> Option D

4. Quick Check:

   Use strings.Contains(s, substr), not s.Contains(substr) [OK]

Hint: Call Contains from strings package, not on string variable [OK]

Common Mistakes:

• Calling methods on string variables as if they were objects
• Forgetting to import strings package
• Assuming Contains returns index

5. Given a list of strings words := []string{"go", "golang", "gopher", "gone"}, which code snippet correctly finds all words containing substring "go" and stores them in result?

hard

A. result := []string{}
for _, w := range words {
if strings.Index(w, "go") > 5 {
result = append(result, w)
}
}

B. var result []string
for i := 0; i < len(words); i++ {
if words[i].Contains("go") {
result = append(result, words[i])
}
}

C. var result []string
for _, w := range words {
if strings.Contains(w, "go") {
result = append(result, w)
}
}

D. result := []string{}
for _, w := range words {
if strings.Index(w, "go") == -1 {
result = append(result, w)
}
}

Solution

1. Step 1: Identify correct substring check

   Use strings.Contains(w, "go") to check if substring exists.

2. Step 2: Append matching words to result slice

   For each word containing "go", append it to result slice.

3. Final Answer:

   var result []string for _, w := range words { if strings.Contains(w, "go") { result = append(result, w) } } -> Option C

4. Quick Check:

   Contains + append in loop = D [OK]

Hint: Use strings.Contains inside loop and append matches [OK]

Common Mistakes:

• Calling Contains as method on string variable
• Appending words that do NOT contain substring
• Checking Index == -1 instead of != -1