力扣面试经典150题（第二十三题）- KMP算法

问题

给你两个字符串 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 仅由小写英文字符组成

我的回答：

/*** @param {string} haystack* @param {string} needle* @return {number}*/
var strStr = function (haystack, needle) {const build_next = (str) => {let common_len = 0;let i = 1;const next = [0];while (i < str.length) {if (str[common_len] == str[i]) {common_len++;next.push(common_len);i++;} else {if (common_len == 0) {next.push(0);i++;} else {common_len = next[common_len - 1];}}}return next;}const next = build_next(needle);let j = 0;for (let i = 0; i < haystack.length;) {if (haystack[i] == needle[j]) {i++;j++;} else if (j > 0) {j = next[j - 1];} else {i++;}if (j == needle.length) {return i - needle.length;}}return -1;
};

解题

这道题本身是一道简单题，直接暴力破解也是可以完成的，但是由这个问题延伸出的KMP算法需要额外提一下，KMP算法能把时间复杂度从原本暴力实现的O(N*M)优化到O(N+M)，本人认为了解并掌握KMP算法是有必要的，在许多比赛或笔试中O(N*M)的时间复杂度是达不到要求的，如果想了解KMP，我推荐这位up主讲解的，感觉还是比较浅显易懂的KMP视频讲解https://www.bilibili.com/video/BV1AY4y157yL/?share_source=copy_web&vd_source=50fd22ef82d5c7ac63b67f5ce42b7454