刷题遇到个kmp算法，以及求next数组的题目，没记得是什么，重新看了一遍这个算法，然后实现了一下。
解决的问题大概是查找一个字符串A是否包含字符串B。暴力o(mn)，即每次不匹配字符串A，B相对位置移动1位。KMP相当于在这个基础上优化，每次不止移动一位，next数组解决的就是每次移动多少相对位置的问题。
最简单的一种情况是，字符串B中没有重复，如abc，则每次不匹配之后可以直接把字符串B的首字符移动至字符串不匹配位置处继续比较，如图（-v- 灵魂画手）
这个比较好理解因为没有重复字符，比较到一个不同就直接从字符串B的首字符重新比较。
吊诡的是，如果字符串B里面有重复就不能直接移动到首位比较，然后问题就是应该移动到哪里。KMP的解决方案是维护一个next数组。以后解释，先直接贴代码
function getNext(str) {
var len = str.length;
var k = -1;
var j = 0;
var next = [-1];
while(j < len) {
if(k==-1 || str[j] == str[k]) {
k++;
j++;
next[j] = k;
}else {
k = next[k]; //from k to next[k] no need to compare
}
}
console.log(next);
return next;
}
function KMP(m, n) {
console.time("KMP:");
var i = 0;
var j = 0;
var next = getNext(n);
while(i < m.length && j < n.length) {
if(j==-1 || m[i] == n[j]) {
i++;
j++;
} else {
j = next[j];
}
}
if(j == n.length) {
console.timeEnd("KMP:");
return (i-j);
}
console.timeEnd("KMP:");
return "not found";
}
数组里存的是每次字符串A，B不匹配时候应该把字符串B移到什么位置，利用这个数组KMP的实现如下：