题目：
实现 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;
}