leetcode-28 找出字符串中第一个匹配项的下标

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function (haystack, needle) {
  let i = 0;
  j = 0;
  while (i < haystack.length) {
    if (haystack[i] === needle[j]) {
      i++;
      j++;
      if (j === needle.length) {
        // 找到haystack的开始
        return i - j;
      }
    } else {
      i = i - j + 1;
      j = 0;
    }
  }
  return -1;
};
// console.log(strStr("sadbutsad", "sad"));

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function (haystack, needle) {
  function buildNext(pattern) {
    const next = Array(pattern.length).fill(0);
    let j = 0;
    for (let i = 1; i < pattern.length; ++i) {
      // 如果不相等j就回退
      // 直到j不能在回退（为零），next[i] = j
      while (j > 0 && pattern[i] !== pattern[j]) {
        j = next[j - 1];
      }
      if (pattern[i] === pattern[j]) {
        j++;
      }
      next[i] = j;
    }
    return next;
  }
  function kmpSearch(text, pattern) {
    if (!pattern) return 0;
    const next = buildNext(pattern);
    let j = 0;
    // 主串
    // 从零位置开始匹配
    for (let i = 0; i < text.length; ++i) {
      while (j > 0 && text[i] !== pattern[j]) {
        // 如果不匹配只回退模式串
        j = next[j - 1];
      }
      if (text[i] === pattern[j]) {
        j++;
      }
      // 如果匹配到结尾，返回匹配的开始索引
      if (j === pattern.length) {
        return i - j + 1;
      }
    }
    return -1;
  }
  return kmpSearch(haystack, needle);
};
// console.log(strStr("sadbutsad", "sad"));