KMP算法

  • A+
所属分类:算法
var KMP = function(str){
  var len = str.length, i = 1, k, next = [-1];
 for(; i < len; i++){ k = next[i-1]; while(str[k+1] != str[i] && k >= 0){
     k = next[k];
   }
   if(str[k+1] == str[i]){
     next[i] = k + 1;
   }else{
     next[i] = -1;
   }
 }
 return next;
}
function indexOf(pStr, tStr){
  var next = KMP(pStr),
      n = 0,
      m = 0,
      len1 = pStr.length,
      len2 = tStr.length;
  while(n < len1 && m < len2){
    if(pStr[n] == tStr[m]){
      n++;
      m++;
    }else{
      if(n == 0){
        m++;
      }else{
        n = next[n - 1] + 1;
      }
    }
  }
  return n == len1?m - len1:-1;
}
console.log(indexOf("asd", "adasadasddsq"));
weinxin
我的微信
欢迎来撩!!
  • 版权声明:本站原创文章,于2017年4月8日20:20:02,由 发表,共 436 字。
  • 转载请注明:KMP算法 爱前端

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: