关于javascript:LeetCode28-实现-strStr-JS-sunday算法

题目

实现 strStr()：

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

示例
输出: haystack = “hello”, needle = “ll”
输入: 2

输出: haystack = “aaaaa”, needle = “bba”
输入: -1

阐明:
当 needle 是空字符串时，咱们该当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时咱们该当返回 0。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

解

先来一个暴力解法

var strStr = function(haystack, needle) {if (needle == "") return 0;
  let j = 0;
  for (let i = 0; i < haystack.length; i++) {if (haystack[i] == needle[j]) {if (j == needle.length - 1) return i-j;
      j++;
    }
    else {i -= j, j = 0;}
  }
  return -1;
};

工夫复杂度 O(mn), 就是两层循环。这种解法低效的起因在于有很多不必要的匹配尝试。很多高效的字符串匹配算法，它们的核心思想都是一样样的，想方法利用已有信息，缩小不必要的尝试。像经典的 KMP 算法应用 next 数组来存储模式串信息来缩小匹配，或者 bm 的好后缀坏字符规定，上面要介绍的 sunday 比前两者都要更简略易懂，在某些状况下也更高效。

sunday 算法在匹配失败时关注的是主串中加入匹配的最末位字符的下一位字符。
如果该字符没有在模式串中呈现则间接跳过，即挪动位数 = 模式串长度 + 1；
否则，使模式串中最初呈现的该字符与其对其，即挪动位数 = 模式串长度 – 该字符最右呈现的地位 (以 0 开始) = 模式串中该字符最右呈现的地位到尾部的间隔 + 1。
上面以主串 ’substring searching’，模式串 ’search’ 为例

不匹配，主串参加匹配的最开端字符的下一个字符，也就是 i 没有呈现在模式串中，那么模式串间接挪动到 i 的下一位

挪动之后不匹配，主串参加匹配的最开端字符的下一个字符，也就是 r 呈现在模式串中，且 最靠后 的地位是 3，那么模式串挪动 6 – 3 = 3

匹配胜利。

复杂度方面，均匀是 O(n)。最坏的状况，每次都往后跳一，而且都是比对到模式串尾才不匹配，这样和暴力差不多，都是 O(mn)，比方 ‘bbbbbbbbbbbbbb’ 和 ’bbcb’, 最好的状况，每次都跳模式串长度 + 1，每次比照都是第一个就不匹配，比方 ‘abcdefghijklmn’ 和 ’xyz’, 这样是 O(m/n)

代码

var strStr = function(haystack, needle) {if (needle == '') return 0

  const map = {}
  const len = needle.length
  for(let i = 0; i < len; i++) {map[needle[i]] = i
  }
  let j = 0
  for(let i = 0; i < haystack.length;) {if (haystack[i + j] == needle[j]) {if (j == len - 1) return i;
      j++;
    } else {let index = map[haystack[i + len]]
      if(index === undefined) {i += len + 1} else {i += len - index}
      j = 0
    }
  }
  return -1
};