28. 实现strStr()-KMP .md

https://www.zhihu.com/question/21923021/answer/281346746

https://leetcode-cn.com/problems/implement-strstr/solution/bang-ni-ba-kmpsuan-fa-xue-ge-tong-tou-ming-ming-ba/

代码

var strStr = function(haystack, needle) {
  return KMP(haystack, needle);
};

function KMP(t, p) {
  let i = 0, j = 0;
  let next = getNext(p);
  while(i < t.length && j < p.length) {
    if (j== -1 || t[i] == p[j]) {
      i++;
      j++;
    } else {
      j = next[j];
    }
  }
  if (j == p.length) {
    return i - j
  }
  return -1;
}

function getNext(p, next = []) {
  next[0] = -1;
  let i = 0, j = -1;
  while(i < p.length) {
    if (j == -1 || p[i] == p[j]) {
      i++;
      j++;
      next[i] = j;
    } else {
      j = next[j];
    }
  }
  return next;
}

复杂度分析

时间复杂度 $O(N+M)$

空间复杂度 $O(M)$