Substring Search Patterns in DSA Go - Execution Trace

Concept Flow - Substring Search Patterns

Start at index 0 in text

↓

Compare substring with text segment

↓

Return index

↓

Done

↓

Repeat

Start checking from the beginning of the text, compare substring at each position, if match found return index, else move forward until end.

Execution Sample

DSA Go

text := "hello world"
pattern := "lo"
for i := 0; i <= len(text)-len(pattern); i++ {
  if text[i:i+len(pattern)] == pattern {
    return i
  }
}
return -1

Search for substring "lo" in "hello world" by checking each possible position.

Execution Table

Step	Operation	Index i	Text Segment Compared	Match?	Action	Result
1	Compare substring at index 0	0	"he"	No	Move to next index	Continue
2	Compare substring at index 1	1	"el"	No	Move to next index	Continue
3	Compare substring at index 2	2	"ll"	No	Move to next index	Continue
4	Compare substring at index 3	3	"lo"	Yes	Return index 3	Found at 3
5	Exit	-	-	-	-	Search ends

💡 Substring found at index 3, search stops.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
i	0	1	2	3	3	3
text segment	"he"	"el"	"ll"	"lo"	"lo"	"lo"
match	false	false	false	true	true	true

Key Moments - 3 Insights

Why do we stop comparing when i > len(text) - len(pattern)?

Because beyond that point, the remaining text is shorter than the pattern, so a match is impossible (see execution_table steps 1-4).

What happens if the substring is not found in the text?

The loop completes without a match and returns -1, indicating no occurrence (not shown in this example but implied after step 5).

Why do we compare text[i:i+len(pattern)] instead of just text[i]?

Because substring matching requires checking a segment equal in length to the pattern, not just a single character (see execution_table column 'Text Segment Compared').

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'i' when the substring is found?

A 4

B 2

C 3

D 1

💡 Hint

Check the 'Index i' column in the row where 'Match?' is Yes.

At which step does the comparison segment equal "ll"?

A Step 3

B Step 2

C Step 4

D Step 1

💡 Hint

Look at the 'Text Segment Compared' column in the execution_table.

If the pattern was "world", at which index would the match be found?

A 7

B 6

C 5

D 4

💡 Hint

Think about where "world" starts in "hello world" and relate to the 'Index i' meaning.

Concept Snapshot

Substring Search Pattern:
- Start from index 0 in text
- Compare substring length segment at each index
- If match, return index
- Else move forward
- Stop when remaining text shorter than pattern
- Return -1 if not found

Full Transcript

This visualization shows how substring search works by checking each possible position in the text for the pattern. We start at index 0 and compare the substring of the text equal in length to the pattern. If it matches, we return the current index. If not, we move to the next index and repeat. We stop when the remaining text is shorter than the pattern because no match is possible beyond that. If no match is found, we return -1. The example searches for "lo" in "hello world" and finds it at index 3.

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