javascript版的KMP算法

流浪天空 2012-12-27

本想提高匹配效率,查资料写了个javascript版的KMP算法,写好后发现我需要的是拼音首字母匹配,不适用,暂存一下。

  1. function match(mainstr,srhstr){//KPM匹配算法,用于快速匹配字符串  
  2.     if(!mainstr||!srhstr)return -1;  
  3.     var l_mainstr=mainstr.length;  
  4.     var l_srhstr=srhstr.length;  
  5.     //构建失配后特征数组  
  6.     var k=0;  
  7.     var vec=new Array();  
  8.     vec[0]=-1;  
  9.     for(i=1;i<l_srhstr;i++){   
  10.         vec[i]=(srhstr[k]==srhstr[i])?vec[k]:k;  
  11.         if(srhstr[i]==srhstr[k])k++;  
  12.         else{k=(srhstr[i]==srhstr[0])?1:0;};  
  13.     }  
  14.     //查找子串  
  15.     i=j=0;  
  16.     while(i<l_mainstr){  
  17.         if(mainstr[i]==srhstr[j]){j++;i++;}  
  18.         else{  
  19.             if(vec[j]==-1){j=0;i++;}  
  20.             else{j=vec[j];}  
  21.         }  
  22.         //是否找到子串  
  23.         if(j==l_srhstr){  
  24.             return i-j;  
  25.         }  
  26.     }  
  27.     return -1;  
  28. }  

相关推荐

henryzhihua / 0评论 2020-06-17