实现strStr

[AILINGANGEL]

输入: haystack 和 needle两个字符串，找出needle在haystack中的位置，如果不存在就返回-1；如果needle是空字符串就返回0；

这是一个字符串匹配的问题，下面的解法是遇到不相等的就将j重置为0,将i设置为下一个；更聪明的做法是采取KMP算法，i的值不用每次都加一, j也不用回到起始位置，避免了无畏的比较.

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

[AILINGANGEL]

KMP算法

var strStr = function(haystack, needle) {
    if(!needle) return 0;
    let i = 0;
    let j = 0;
    let next = getNext(needle);
    while(i<haystack.length && j<needle.length) {
        if(j === -1 || haystack[i] === needle[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    if(j === needle.length) {
        return i - j;
    }
    return -1;
};

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