【力扣】28. 找出字符串中第一个匹配项的下标

给你两个字符串 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 。

提示：

• 1 <= haystack.length, needle.length <= 104
• haystack 和 needle 仅由小写英文字符组成

题解：

KMP 算法：

// 时间复杂度：O(m+n) 其中 m 是文本字符串 haystack 的长度，n 是模式串 needle 的长度
// 空间复杂度：O(n) 其中 n 是模式串 needle 的长度
func strStr(haystack string, needle string) int {
	n := len(needle)
	next := make([]int, n)
	// 生成前缀表
	getNext(next, needle)
	j := 0
	for i := 0; i < len(haystack); i++ {
		// 如果 haystack[i] 和 needle[j] 不匹配，那么 j 跳到 next[j-1] 的位置
		for j > 0 && haystack[i] != needle[j] {
			j = next[j-1]
		}
		// 如果 haystack[i] 和 needle[j] 匹配，那么 j 增加 1
		if haystack[i] == needle[j] {
			j++
		}
		// 如果 j 等于 n，说明 needle 完全匹配
		// 此时返回 i - n + 1，即 needle 在 haystack 中的起始位置
		if j == n {
			return i - n + 1
		}
	}
	// 如果遍历完 haystack 都没有找到完全匹配的 needle，那么返回 -1
	return -1
}

// getNext 用于生成前缀表.
func getNext(next []int, s string) {
	j := 0
	// 前缀表的第一位默认为 0
	next[0] = 0
	for i := 1; i < len(s); i++ {
		// 如果 s[i] 和 s[j] 不匹配，并且 j 大于 0，那么 j 跳到 next[j-1] 的位置
		for j > 0 && s[i] != s[j] {
			j = next[j-1]
		}
		// 如果 s[i] 和 s[j] 匹配，那么 j 增加 1
		if s[i] == s[j] {
			j++
		}
		// 记录到 i 位置为止的最长公共前后缀的长度
		next[i] = j
	}
}