Topic link
Problem Solving using KMP algorithm (submitted and approved)
func strStr(haystack string, needle string) int {
return firstIndex(haystack, needle)
}
// Find the index of the first occurrence of Pattern in text. If not, return -1.
// Convention: Return 0 as long as pattern is an empty string
func firstIndex(text, pattern string) int {
if pattern == "" {
return 0
}
if text == "" {
return - 1
}
// text ! = "" && pattern ! = ""
if len(text) < len(pattern) {
return - 1
}
// tl >= pl
return indexKMP(text, pattern)
}
func indexKMP(text, pattern string) int {
var (
ti int
pi int
tl = len(text)
pl = len(pattern)
next = getNextArray(pattern)
)
for ti < tl {
if text[ti] == pattern[pi] {
ti++
pi++
if pi == pl {
return ti-pl
}
} else if pi == 0 {
ti++
if tl-ti < pl {
break}}else {
pi = next[pi- 1]
if tl-ti < pl-pi {
break}}}return - 1
}
func getNextArray(p string) []int {
// Preconditions: p is not an empty string
if p == "" {
panic("p is empty")}var (
j int // Prefix the current index
i = 1 // suffix current index
l = len(p)
next = make([]int, l)
)
// next[0] = 0, implicit initialization
for i < l {
if p[j] == p[i] {
j++
next[i] = j
i++
} else if j == 0 {
next[i] = 0
i++
} else {
j = next[j- 1]}}return next
}
Copy the code