JavaScript 版本KMP

李恒道

https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/solutions/732461/dai-ma-sui-xiang-lu-kmpsuan-fa-xiang-jie-mfbs/

减1版本

const generateNext = (str) => {
  const arr = [-1];
  let j = -1;
  for (let i = 1; i < str.length; i++) {
    const char = str[i];
    while (j >= 0 && char != str[j + 1]) {
      j = arr[j];
    }
    if (char == str[j + 1]) {
      j++;
    }
    arr[i] = j;
  }
  return arr;
};
/**
 * @param {string} haystack
 * @param {string} needle
 * @Return {number}
 */
var strStr = function (haystack, needle) {
  const next = generateNext(needle);
  let j = -1;
  for (let index = 0; index < haystack.length; index++) {
    const char = haystack[index];
    while (j >= 0 && char !== needle[j + 1]) {
      j = next[j];
    }
    if (char == needle[j + 1]) {
      j++;
    }
    if(j==needle.length-1){
        return index-j
    }
  }
  return -1
};
console.log(strStr("hello",'ll'));

不减1

const generateNext = (str) => {
  const arr = [0];
  let j = 0;
  for (let i = 1; i < str.length; i++) {
    const char = str[i];
    while (j > 0 && char != str[j]) {
      j = arr[j-1];
    }
    if (char == str[j]) {
      j++;
    }
    arr[i] = j;
  }
  return arr;
};
/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function (haystack, needle) {
  const next = generateNext(needle);
  let j = 0;
  for (let index = 0; index < haystack.length; index++) {
    const char = haystack[index];
    while (j > 0 && char !== needle[j]) {
      j = next[j-1];
    }
    if (char == needle[j]) {
      j++;
    }
    if (j == needle.length) {
      return index - j+1;
    }
  }
  return -1;
};