KMP

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 }

Sunday

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
}