問題

給你兩個字符串?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