2
go 实现indexOf，leetCode28
source link: https://studygolang.com/articles/35577
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
go indexOf
indexOf
indexOf(s, p string) 函数会返回p在s中首次出现的位置，倘如没有则返回-1，本次使用之前提到过的kmp算法来作为indexOf的核心，并用来解决leetcode28题
func strStr(haystack string, needle string) int {
return indexOf(haystack, needle)
}
func indexOf(s, p string) int {
if len(p) == 0 {
return 0
}
next := make([]int, len(p))
next[0] = -1
j := -1
for i := 1; i < len(p); i++ {
for j != -1 && p[i] != p[j+1] {
j = next[j]
}
if p[i] == p[j+1] {
j++
}
next[i] = j
}
j = -1
for i := 0; i < len(s); i++ {
for j != -1 && s[i] != p[j+1] {
j = next[j]
}
if s[i] == p[j+1] {
j++
}
if j == len(p) - 1 {
return i - j
}
}
return -1
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK