carloscn
commented
1 year ago 问题分析
采用KMP算法：
KMP算法一种改进的模式匹配算法，是D.E.Knuth、V.R.Pratt、J.H.Morris于1977年联合 发表，KMP算法又称克努特-莫里斯-普拉特操作。它的改进在于：每当从某个起始位置开始一趟比较后，在匹配过程中出现失配，不回溯i，而是利用已经得到的部分匹配结果，将一种假想的位置定位“指针”在模式上 向右滑动尽可能远的一段距离到某个位置后，继续按规则进行下一次的比较。
问题描述
给你两个字符串 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 仅由小写英文字符组成
来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string