在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]的值,
- 如果nextArrStr [k]和nextArrStr[j]相等,那next[j+1] = k+1
- 如果nextArrStr [k]和nextArrStr[j]不相等,那么我们就往前找上一个前后缀(也就是next[k]),因为nextArrStr的0到k和j-k到j是一样的,我们只需要进入第一步判断nextArrStr[next[k]]和nextArrStr[j]是否相等即可
参考资料 KMP NEX详解
