KMP算法 获取前缀next数组 并且实现KMP算法

KMP算法 获取前缀next数组 并且实现KMP算法 KMP算法整体思路是参考的B站UP的 点这里去观看视频

function getNext(pattern){
    let next = [];
    let j = 0;//j指针最开始在0位置；
    let k = -1; //第一个k的值为-1   k代表的是上一个的回退位置
    next[0] = k; //next数组中存储的就是所有的k，next[0]也就是存储的第一个k，即为-1；
    while(j < pattern.length - 1 ){
        if(k === - 1 || pattern[k] === pattern[j]){
        	// 接下来要存储next[1] next[2]... 所以必须是++j  先自增。
        	//因为k代表的是上一个回退位置，所以使用++k求得 本次的值  然后进行对next数组赋值
            next[++j] = ++k;
        }else{
            k = next[k]
        }
    }
    return next
}



function KMP(str,sub){
    if(str==="" || sub === "")return -1;
    const strLen = str.length,subLen = sub.length;
    let i = 0,j = 0;
    const next = getNext(sub);
    //只要有一个的下表大于等于长度 那么就表示没有查找到
    while(i < strLen && j < subLen){
    //因为j有可能跳到next数组的第一个位置那个时候j 就为 -1
        if(j === - 1 || str[i] === sub[j]){
        //相等就同时自增
            i++;
            j++;
        }else{
		//不相等就让j进行回退
            j = next[j]
        }
    }
    return j >= subLen ? i - j : -1
}