实现 strStr()
题目
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
示例 1：
输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。示例 2：
输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。思路
使用 KMP : 当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。
解法
方法一:前缀表使用减1实现
// getNext 构造前缀表next
// params:
// next 前缀表数组
// s 模式串
func getNext(next []int, s string) {
j := -1 // j表示 最长相等前后缀长度
next[0] = j
for i := 1; i < len(s); i++ {
for j >= 0 && s[i] != s[j+1] {
j = next[j] // 回退前一位
}
if s[i] == s[j+1] {
j++
}
next[i] = j // next[i]是i（包括i）之前的最长相等前后缀长度
}
}
func strStr(haystack string, needle string) int {
if len(needle) == 0 {
return 0
}
next := make([]int, len(needle))
getNext(next, needle)
j := -1 // 模式串的起始位置 next为-1 因此也为-1
for i := 0; i < len(haystack); i++ {
for j >= 0 && haystack[i] != needle[j+1] {
j = next[j] // 寻找下一个匹配点
}
if haystack[i] == needle[j+1] {
j++
}
if j == len(needle)-1 { // j指向了模式串的末尾
return i - len(needle) + 1
}
}
return -1
}方法二: 前缀表无减一或者右移
// getNext 构造前缀表next
// params:
// next 前缀表数组
// s 模式串
func getNext(next []int, s string) {
j := 0
next[0] = j
for i := 1; i < len(s); i++ {
for j > 0 && s[i] != s[j] {
j = next[j-1]
}
if s[i] == s[j] {
j++
}
next[i] = j
}
}
func strStr(haystack string, needle string) int {
n := len(needle)
if n == 0 {
return 0
}
j := 0
next := make([]int, n)
getNext(next, needle)
for i := 0; i < len(haystack); i++ {
for j > 0 && haystack[i] != needle[j] {
j = next[j-1] // 回退到j的前一位
}
if haystack[i] == needle[j] {
j++
}
if j == n {
return i - n + 1
}
}
return -1
}