题目

题目来源：力扣（LeetCode）

实现 strStr() 函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。

说明：

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。


示例 1：

输入：haystack = “hello”, needle = “ll”
输出：2
示例 2：

输入：haystack = “aaaaa”, needle = “bba”
输出：-1
示例 3：

输入：haystack = “”, needle = “”
输出：0

思路分析

KMP 算法

KMP的经典思想就是:当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。

KMP 算法详解

  1. /**
  2.  * @param {string} haystack
  3.  * @param {string} needle
  4.  * @return {number}
  5.  */
  6. var strStr = function (haystack, needle) {
  7.   if (needle.length === 0) {
  8.     return 0;
  9.   }
  10.   const next = new Array(needle.length);
  11.   getNext(next, needle);
  12.   let j = -1; // // 因为next数组里记录的起始位置为-1
  13.   for (let i = 0; i < haystack.length; i++) { // 注意i就从0开始
  14.     while (j >= 0 && haystack[i] != needle[j + 1]) { // 不匹配
  15.       j = next[j]; // j 寻找之前匹配的位置
  16.     }
  17.     if (haystack[i] == needle[j + 1]) { // 匹配，j和i同时向后移动
  18.       j++; // i的增加在for循环里
  19.     }
  20.     if (j == (needle.length - 1)) { // 文本串s里出现了模式串t
  21.       return (i - needle.length + 1);
  22.     }
  23.   }
  24.   return -1;
  25. };
  27. // 前缀表统一减一
  28. function getNext(next, s) {
  29.   let j = -1;
  30.   next[0] = j;
  31.   for (let i = 1; i < s.length; i++) { // 注意i从1开始
  32.     while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
  33.       j = next[j]; // 向前回溯
  34.     }
  35.     if (s[i] == s[j + 1]) { // 找到相同的前后缀
  36.       j++;
  37.     }
  38.     next[i] = j; // 将j（前缀的长度）赋给next[i]
  39.   }
  40. }