简单粗暴上代码

KMP的原理我就不讲了，想转过弯儿来不容易，建议大家先学会了怎么推导出next数组规律，然后准备两张纸，大纸上写上一行你要匹配的目标字符串，并分别写出位置编号，小纸上写上一行，也写上位置编号和对应的next数组编号，然后移动小纸片模拟匹配过程，你就会了。（用画图模拟也行）

从以上推导过程就能发现KMP算法的规律，得到如下代码：

推导next数组代码：

function KMPfunc(str) {         var len = str.length;         var j = -1, i = 0;         var next = [-1];         while (i < len) {             if (j == -1 || str[i] === str[j]) {                 j++;                 i++;                 //next[i] = j;                 next.splice(i, 1, j);             }             else {                 //j = next[j];                 j = next.slice(j,j+1);             }         }         next.shift();         return next;     }

KMP字符匹配算法

String.prototype.KMPsearch = function (str) {         var len = str.length;         var sstr = this.toString();         var slen = sstr.length;         var i = 0, j = 0, k = 0;         if (slen > 1) {             var next = KMPfunc(this.toString());             while (i < len) {                 if (str[i] === sstr[j]) {                     if (j == (slen - 1)) {                         if (i == (len - 1)) {                             return k + 1;                         }                         else {                             k++;                             j = 0;                         }                     }                     else {                         j++;                         i++;                     }                 }                 else if (i == (len - 1) && str[i] != sstr[i]) {                     return k;                 }                 else {                     if (j == 0) {                         i++;                     }                     else {                         j = next[j - 1];                     }                 }             }         }         else {             for (var i = 0; i < len; i++) {                 if (sstr == str[i]) {                     k++;                 }             }             return k;         }     };

另辟蹊径的KMP next数组推导及next数组优化

此种写法思路主要是以对称前后缀的分析方法构建代码，实现next数组

function getNext(str){    var arr=[0,1];    for(var i=1;i