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

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

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