javascript实现KMP算法（没啥实用价值，只供学习）

浏览数：15 / 时间：2015年06月08日

简单粗暴上代码

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;
         }
     };