Substring Search Patterns in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Naive Substring Search

What is the output of this Go code that searches for all occurrences of a pattern in a text using a naive approach?

DSA Go

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

A [7]

B [0 3 7]

C [3 7]

D [0 7]

💡 Hint

Check where the pattern "abra" fully matches in the text "abracadabra".

The naive search checks every position in the text where the pattern could start. The pattern "abra" appears at index 0 and again at index 7 in "abracadabra". So the output is [0 7].

❓ Predict Output

intermediate

Output of KMP Prefix Table Construction

What is the output of this Go code that builds the prefix table (also called lps array) for the pattern "ababaca"?

DSA Go

package main
import "fmt"
func buildLPS(pattern string) []int {
    lps := make([]int, len(pattern))
    length := 0
    i := 1
    for i < len(pattern) {
        if pattern[i] == pattern[length] {
            length++
            lps[i] = length
            i++
        } else {
            if length != 0 {
                length = lps[length-1]
            } else {
                lps[i] = 0
                i++
            }
        }
    }
    return lps
}
func main() {
    pattern := "ababaca"
    fmt.Println(buildLPS(pattern))
}

A [0 0 1 2 3 0 1]

B [0 1 0 1 2 3 0]

C [0 0 1 2 3 1 0]

D [0 0 1 2 3 0 0]

💡 Hint

The lps array stores the length of the longest prefix which is also suffix for each prefix of the pattern.

The prefix table for "ababaca" is [0 0 1 2 3 0 1]. This means at each index, the length of the longest proper prefix which is also suffix is stored.

🔧 Debug

advanced

Find the error in this Rabin-Karp hash update code

This Go code tries to update the rolling hash in Rabin-Karp substring search. What error will it cause when run?

DSA Go

package main
import "fmt"
func rabinKarpUpdateHash(oldHash int, leftChar, rightChar byte, h, q int) int {
    newHash := (oldHash - int(leftChar)*h) * 256
    newHash = (newHash + int(rightChar)) % q
    if newHash < 0 {
        newHash += q
    }
    return newHash
}
func main() {
    oldHash := 100
    leftChar := byte('a')
    rightChar := byte('b')
    h := 1
    q := 101
    fmt.Println(rabinKarpUpdateHash(oldHash, leftChar, rightChar, h, q))
}

A 0

B Incorrect hash value due to wrong h calculation

C Produces a negative hash value

D runtime error: invalid operation

💡 Hint

Check how h is calculated and used in rolling hash update.

The variable h should be precomputed as (256^(m-1)) % q where m is the pattern length. Here h=1 is incorrect, so the hash update will produce wrong values.

🧠 Conceptual

advanced

Time complexity of KMP algorithm

What is the worst-case time complexity of the Knuth-Morris-Pratt (KMP) substring search algorithm for a text of length n and pattern of length m?

A O(n + m)

B O(n * m)

C O(n * log m)

D O(m * log n)

💡 Hint

KMP uses a prefix table to avoid rechecking characters.

KMP runs in linear time relative to the sum of text and pattern lengths, so O(n + m).

🚀 Application

expert

Find all starting indices of pattern in text using Rabin-Karp

Given the following Go code implementing Rabin-Karp substring search, what is the output when searching for pattern "test" in text "this is a test text with test cases"?

DSA Go

package main
import "fmt"
func rabinKarpSearch(text, pattern string) []int {
    var result []int
    n, m := len(text), len(pattern)
    if m > n {
        return result
    }
    q := 101
    h := 1
    for i := 0; i < m-1; i++ {
        h = (h * 256) % q
    }
    pHash, tHash := 0, 0
    for i := 0; i < m; i++ {
        pHash = (256*pHash + int(pattern[i])) % q
        tHash = (256*tHash + int(text[i])) % q
    }
    for i := 0; i <= n-m; i++ {
        if pHash == tHash {
            match := true
            for j := 0; j < m; j++ {
                if text[i+j] != pattern[j] {
                    match = false
                    break
                }
            }
            if match {
                result = append(result, i)
            }
        }
        if i < n-m {
            tHash = (256*(tHash-int(text[i])*h) + int(text[i+m])) % q
            if tHash < 0 {
                tHash += q
            }
        }
    }
    return result
}
func main() {
    text := "this is a test text with test cases"
    pattern := "test"
    fmt.Println(rabinKarpSearch(text, pattern))
}

A [11 26]

B [11 25]

C [10 25]

D [10 26]

💡 Hint

Check the exact indices where "test" appears in the text string.

The pattern "test" appears starting at index 10 and index 25 in the text. The Rabin-Karp algorithm finds these indices correctly.

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