首页 > 代码库 > KMP算法分析
KMP算法分析
KMP是一种复杂度较低的字符串比较算法。基本思路是对欲匹配字符串进行预处理，分析当k位匹配时可以后移的位数，所得的数构成该字符串的特征向量。
求特征向量Next
1 int* Next(string p){ 2 int m=p.length(); 3 int *N=new int[m]; 4 N[0]=0; 5 for(int i=1;i<m;i++){ 6 int k=N[i-1]; 7 while(k>0&&P[i]!=P[k])k=N[k-1]; 8 if(P[i]==P[k]) N[i]=k+1; 9 else N[i]=0;10 }11 return N;12 }
分析：边界N[0]=0;
从第1位开始向后构造N[i]:设临时变量k，令k为i-1位匹配时后移位数，如果第i位和第k为不匹配，k向前回溯，直到匹配或者k=0无法后移。处理后如果k位和i位匹配，N[i]则可在k匹配后后移1位，否则无法后移，N[i]=0
匹配的具体实现:
1 int KMP(string T,string P,int *N,int startIndex){ 2 int lastIndex=T.length()-P.length(); 3 if((startIndex-lastIndex)>=0) return -1; 4 int pt,pp=0; 5 for(pt=startIndex;pt<T.length();pt++){ 6 while(P[pp]!=T[pt]&&pp>0) pp=N[pp-1]; 7 if(P[pp]==T[pt]) pp++; 8 if(pp==P.length())return pt; 9 }10 return -1;11 }
分析：
比较时一旦现有指向不匹配，pp立刻转回前一位继续与pt进行匹配，直到匹配上或者边界。匹配上则pp++进行下一位匹配。
KMP算法分析
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。