Leetcode-in-JavaScript

# [28] 实现 strStr()

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。

示例 1:

输入: haystack = "hello", needle = "ll"

输出: 2

示例 2:

输入: haystack = "aaaaa", needle = "bba"

输出: -1

# 朴素算法

这题考察对字符串的遍历操作。使用快慢指针的方式，慢指针遍历haystack的每一个字符，每次循环都要使用快指针向前预测以该字符为首的子串是否与neddle字符串一一匹配，不匹配时中断预测匹配，后移haystack的指向字符进行下一次匹配。

var strStr = function(haystack, needle) {
  const len1 = haystack.length;
  const len2 = needle.length;
  if (len2 === 0) return 0;
  if (len1 < len2) return -1;

  for (let i = 0; i <= len1 - len2; i++) {
    let j = 0;
    while (j < len2) {
      if (haystack[i + j] !== needle[j]) {
        break;
      }
      j++;
    }
    if (j === len2) {
      return i;
    }
  }
  return -1;
};

这样解固然能AC，但这样的时间复杂度并不是O(n)，它之中伴随着大量的回溯。最坏情况是haystack是重复多次的只有最后一位与neddle不同的字符串，那么每次子串匹配到最后才会发现不匹配，又得从头的下一位开始匹配，最坏时间复杂度将达到O(mn)。

# KMP算法

我们需要更高级的效率更高的算法来优化它。这就是有名的KMP算法。KMP算法的优势在于遇到不匹配的情况下，不用暴力回溯，算出模式串的最长公共前后缀，将指针从前缀起始位置移动到后缀起始位置，就能直接继续接下来的匹配，时间将会是O(m+n)。KMP算法另一个的好处就是只需要对模式串预先做一次处理，就可以对多个字符串做匹配了。在数据量较大的情况下是个很划算的操作。因此在工业界经常被采用。

KMP的具体实现方式是：借助一个next数组记录模式串neddle的确定有限状态自动机信息，再使用这个确定有限状态自动机去匹配不同的待匹配字符串。

所谓确定有限状态自动机，这是一个专业名词，简单来说就是当操作进行到其中的一个状态时，对下一步动作存在有限的几种可能，并且每一种可能都能回到之前经历的某一步操作，这个过程是确定的。

对于字符串匹配来说，就是判断下一个出现的字符是什么，把出现的每一种可能链接到之前能正确匹配到的模式串最长前缀子串的位置尾部。

在进行字符串匹配时，若当前字符串与模式串在第j位发生失配，则参考next数组，将模式串位置右移j - next[j]位，继续向后匹配。这样做就减少j - next[j]次的多余比较，提高了匹配效率。


// KMP算法
var strStr = function(haystack, needle) {
  if (needle.length === 0) return 0;

  needle = ' ' + needle;
  const next = KMP(needle);

  const len1 = haystack.length;
  const len2 = needle.length;

  let i = 0;
  let j = 1;
  while (i < len1 && j < len2) {
    if (j === 0 || haystack[i] === needle[j]) {
      // 若当前字符匹配成功，则进行下一字符的匹配
      i++;
      j++;
    } else {
      // 若不匹配，如果前面有已匹配字符子串，j从后缀尾回退到前缀尾，即模式串向右移动`j - next[j]`位
      j = next[j];
    }
  }

  // 匹配成功，返回子串的位置，否则返回-1
  return j === len2 ? i - j + 1 : -1;
};

// 构建确定有限状态转移表next
// 用于生成next数组。其含义为：当前字符之前的字符串中，最大公共前后缀的长度。
//             0   j = 0
// next[j] =   1   公共前后缀长度为0
//             最大公共前后缀长度
function KMP(pattern) {
  const next = [0, 0];
  let i = 1;
  let j = 0;

  while (i < pattern.length) {
    // pattern[j]表示前缀尾，pattern[i]表示后缀尾
    if (j === 0 || pattern[i] === pattern[j]) {
      i++;
      j++;
      next[i] = j;
    } else {
      j = next[j];
    }
  }

  return next;
}

← [42] 接雨水 →