在leetcode看到了一道字符串查找的问题,我们来使用KMP算法解决这道题,我们先写出来这道题的解法,然后再详细解释一下next 是怎么求出来的.

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

输入: haystack = "hello", needle = "ll"
输出: 2

var strStr = function(haystack, needle) {

var next = getNextArr(needle);
var hasyArr = haystack.split('');
var needleArr = needle.split('');
var i = 0;
var j = 0;
    while(i<hasyArr.length&&j<needleArr.length){
          if(j==-1||hasyArr[i]==needleArr[j]){
             i++;
             j++;
             }else{
                 j=next[j]
             }

        
}
    

        if(j==needleArr.length){
        return i-j
    }else{
        return -1;
    }

    
};

var getNextArr = function (nextStr){
    var nextArr = nextStr.split('');
    var nextArrStr = nextStr.split('');
    var j = 0;
    var k = -1;
    
    nextArr[0]=-1
    while(j<nextArr.length-1){
          if(k===-1||nextArrStr[k] ==nextArrStr[j] ){
             nextArr[++j] = ++k;
             }else{
                 k=nextArr[k];
             }
    }
    
    return nextArr

}

对next的理解

我们首先把nex里面的几个地方的值通过log输出出来

var getNetArr = function (nextStr){
    var nextArr = nextStr.split('');
    var nextArrStr = nextStr.split('');
    var j = 0;
    var k = -1;
    
    nextArr[0]=-1
    while(j<nextArr.length-1){console.log('while',j,k);
          if(k===-1||nextArrStr[k] ==nextArrStr[j] ){console.log('addNex  ',j+1,k+1);
             nextArr[++j] = ++k;

             }else{
                 k=nextArr[k];console.log('change_k    ',j,k)
             }
    }
    
    return nextArr

}

getNetArr('ababcbabc')得到输出

image.png

我们可以看到,当我们求next[j+1]的时候,
就是找从0到j这个子串的最大前后缀,
通过分辨两种情况决定next[j+1]的值,

1. 如果nextArrStr [k]和nextArrStr[j]相等,那next[j+1] = k+1
2. 如果nextArrStr [k]和nextArrStr[j]不相等,那么我们就往前找上一个前后缀(也就是next[k]),因为nextArrStr的0到k和j-k到j是一样的,我们只需要进入第一步判断nextArrStr[next[k]]和nextArrStr[j]是否相等即可

参考资料 KMP NEX详解