题目：
实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例 1:
输入: haystack = "hello", needle = "ll"
输出: 2
示例 2:
输入: haystack = "aaaaa", needle = "bba"
输出: -1
说明:
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
方法一：双指针
var strStr = function(haystack, needle) {
let left = 0, right = 0;
let len_h = haystack.length;
let len_n = needle.length;
if(len_h < len_n)
return -1;
if(len_n === 0)
return 0;
while(right < len_h){
if(haystack[right] === needle[left]){
left++;
if(left === len_n)
return right - left + 1
}else{
right = right - left ;
left = 0;
}
right++;
}
return -1;
};
方法二：Sunday算法
Sunday详见
https://blog.csdn.net/q547550831/article/details/51860017
var strStr = function(haystack, needle) {
let map = {};
let len_n = needle.length;
let len_h = haystack.length;
for(let i = 0; i < len_n; i++){
map[needle[i]] = len_n - i;
}
if(needle === '')
return 0;
if(haystack === needle)
return 0;
if(len_n > len_h)
return -1;
let i = 0;
while(i <= len_h - len_n){
let temp = 0;
for(let j = 0; j < len_n; j++){
if(haystack[i + temp] === needle[j]){
temp++
}else{
break;
}
}
if(temp === len_n)
return i;
i += (map[haystack[i + len_n]] || len_n);
}
return -1
};
方法三：KMP
思路详见
极客学院 KMP 算法
let GetNextval = (p) => {
let next = []
let pLen = p.length;
next[0] = -1;
let k = -1;
let j = 0;
while (j < pLen - 1){
//p[k]表示前缀，p[j]表示后缀
if (k == -1 || p[j] == p[k]){
++j;
++k;
//较之前next数组求法，改动在下面4行
if (p[j] != p[k])
next[j] = k; //之前只有这一行
else
//因为不能出现p[j] = p[ next[j ]]，所以当出现时需要继续递归，k = next[k] = next[next[k]]
next[j] = next[k];
}else {
k = next[k];
}
}
return next;
}
let strStr = (s, p) =>{
let i = 0;
let j = 0;
let next = GetNextval(p)
let sLen = s.length;
let pLen = p.length;
while (i < sLen && j < pLen) {
//①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++
if (j == -1 || s[i] == p[j]){
i++;
j++;
}else{
//②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]
//next[j]即为j所对应的next值
j = next[j];
}
}
if (j == pLen)
return i - j;
else
return -1;
}
方法四：KMP
时间超出限制
KMP详见
阮一峰 字符串匹配的KMP算法
let getNext = (str) => {
let arr = []
for(let i = 0, len = str.length; i < len; i++){
let cur = str.slice(0, i + 1);
for(let j = 0; j < i; j++){
if(i < 1){
arr[i] = 0
break;
}else{
let pre = cur.slice(0, j + 1);
let sub = cur.slice(- j - 1);
if(pre === sub){
arr[i] = j + 1;
}
}
}
arr[i] = arr[i] || 0;
}
return arr;
}
let strStr = (haystack, needle) => {
let i = 0;
let len_n = needle.length;
let len_h = haystack.length;
if(needle === '')
return 0;
if(haystack === needle)
return 0;
if(len_n > len_h)
return -1;
let nextMap = getNext(needle);
while(i < len_h){
for(var j = 0; j < len_n; j++){
if(haystack[i + j] === needle[j]){
if(j === len_n - 1)
return i;
}else{
break;
}
}
if(j)
i += (j - nextMap[j - 1])
else
i++;
}
return -1;
}
