1 func KMP(str, substr string) int {

 2    if substr == "" {

 3       return 0

 4    }

 5    strLen := len(str)

 6    subLen := len(substr)

 7    next := make([]int, subLen)

 8    for i, j := 1, 0; i < subLen; i++ {

 9       for j > 0 && substr[i] != substr[j] {

10          j = next[j-1]

11       }

12       if substr[i] == substr[j] {

13          j++

14       }

15       next[i] = j

16    }

17    for i, j := 0, 0; i < strLen; i++ {

18       for j > 0 && str[i] != substr[j] {

19          j = next[j-1]

20       }

21       if str[i] == substr[j] {

22          j++

23       }

24       if j == subLen {

25          return i - subLen + 1

26       }

27    }

28    return -1

29 }

func Sunday(str, substr string) int {

   if len(substr) == 0 {

      return 0

   }

   strLen := len(str)

   subLen := len(substr)

   if subLen > strLen {

      return -1

   }

   m := make(map[rune]int, 0)

   for index, c := range substr {

      m[c] = index

   }

   start, compareCount := 0, 0

   for start+subLen <= strLen {

      compareCount = 0

      for str[start+compareCount] == substr[compareCount] {

         compareCount++

         if compareCount == subLen {

            return start

         }

      }

      checkIndex := start + subLen

      var lastIndex int

      if checkIndex < strLen {

         lastIndex = m[rune(str[checkIndex])]

      } else {

         lastIndex = -1

      }

      if lastIndex != -1 {

         start += subLen - lastIndex

      } else {

         start += start + subLen + 1

      }

   }

   return -1

}