KMP算法分析
浏览数：21 /
时间：2015年06月08日
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++进行下一位匹配。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
