func buildNext(pattern string) []int {
 next := make([]int, len(pattern))
 j := 0
 for i := 1; i < len(pattern); i++ {
  for j > 0 && pattern[i] != pattern[j] {
   j = next[j-1]
  }
  if pattern[i] == pattern[j] {
   j++
  }
  next[i] = j
 }
 return next
}

func strStr(haystack string, needle string) int {
 if len(needle) == 0 {
  return 0
 }

 next := buildNext(needle)
 j := 0

 for i := 0; i < len(haystack); i++ {
  for j > 0 && haystack[i] != needle[j] {
   j = next[j-1]
  }
  if haystack[i] == needle[j] {
   j++
  }
  if j == len(needle) {
   return i - len(needle) + 1
  }
 }

 return -1
}