kmp.js

const getNext = str => {
  let len = str.length;
  let next = [-1];
  let i = 0;
  let p = -1;

  while (i < len) {
    if (p === -1 || str[i] === str[p]) {
      next[++i] = ++p;
    } else {
      p = next[p];
    }
  }

  return next;
};

const strStr = (str, patten) => {
  if (patten === "") {
    return 0;
  }

  let next = getNext(patten);
  let m = str.length;
  let n = patten.length;
  let i = 0;
  let j = 0;

  while (i < m && j < n) {
    if (j === -1 || str[i] === patten[j]) {
      i++;
      j++;
    } else {
      j = next[j];
    }
  }

  return j === n ? i - j : -1;
};

参考：KMP字符串匹配算法

leetcode #28