KMP算法
KMP算法 匹配时间为Θ(n) ,只用到辅助函数next ,它在Θ(m)时间内根据模式预先计算出来,并且存储在数组next[1.....m]中。数组next使得我们按需要“及时”有效计算转移函数δ。粗略的说,对任意状态q=0,1,2,....m和任意字符a∈∑ ,next[q]的值包含了与a无关当在计算δ(q,a)的信息。由于next只有m个元素,而δ有m|∑|个值,所以通过预先计算next而不是δ,可以使计算时间减少一个因子。
关于模式的前缀函数next包含模式与其自身的偏移进行匹配的信息。这些信息可用在朴素的字符串匹配算法中避免对无用偏移进行检测,也可以避免在字符串匹配自动机中,对整个转移函数δ的预先计算。
下面给出KMP算法流程
为了便于理解 ,字符串都从P[1....m], T[1....n];
i初始值为0
j初始值为0
假设现在文本串T匹配到 i 位置,模式串P匹配到 j 位置
(1) 若 j>0 且T[ i+1 ] != P[ j+1 ],则 T [ i-j+1,....i ] == P[ 1....j ]肯定是成立的,根据这个条件,如果我们能找到一个k<j 值,使得 T[ i-k+1.....i] == P[ 1.....k ],那么我们可以令j=k ,再 回到(1)步,判断 T[i+1]==P[j+1],其实k值就是当模式串指在 j 时,P[1.....k] 即是]P[ 1.....j ]的前缀也是T [ i-j+1,......i ]的后缀 ,即 P[1....k-1 ] ?T [ i-j,......i ] 求最大k值 。又因为 T [ i-j+1,......i ]==P[ 1......j ] 我们可以写成 P[ 1....k ] ?P [ 1....j ],因此我们可以用一个next数组来表示k ,k=next[j];
(2) 若 T[ i+1 ]==P[ j+1 ] 则i++,j++,继续匹配下一个字符
(3) 若j==strlen(P)则匹配成功 j=next[j]
下面用伪代码表示KMP算法
KMP_Matcher(char *T,char*P){ n=T.length; m=L=P.length; int* next = Compute_Prefix_Function(P); j=0; for(int i=0;i<n;i++){ while(j>0&&P[j+1]!=T[i+1]) j=next[j]; if(P[j+1]==T[i+1]){ j+=1; } if(j==m){ cout<<"Pattern occurs whit shift "<<i-m<<endl; j=next[j]; } } }
求next数组 即next[q]是Pq的真后缀P的最长前缀长度
Compute_Prefix_Function(char*P){ int m=P.length; int *next = new int[m+1]; next[1]=0; //Pq的真后缀P的最长缀长度 int k=0; for(int i=2;i<=m;i++){ //i个字符以匹配成功 while(k>0&&P[k+1]!=P[i]) //没有匹配成功 k=next[k]; if(P[k+1]==P[i]) k+=1; next[i]=k; } return next; }
下面给出完成的程序
为了便于理解,模式字符串是P[1....m],文本字符串是T[1....m]
#include<iostream> #include<string.h> using namespace std; int* Compute_Prefix_Function(char*P){ int m=strlen(P)-1; int *next = new int[m+1]; next[1]=0; int k=0; for(int i=2;i<=m;i++){ while(k>0&&P[k+1]!=P[i]) //没有匹配成功 k=next[k]; if(P[k+1]==P[i]) k+=1; next[i]=k; } for(int i=1;i<=m;i++) cout<<next[i]<<endl; return next; } void KMP_Matcher(char *T,char*P){ int n=strlen(T)-1; int m=strlen(P)-1; int* next = Compute_Prefix_Function(P); int j=0; for(int i=0;i<n;i++){ while(j>0&&P[j+1]!=T[i+1]) j=next[j]; if(P[j+1]==T[i+1]){ j+=1; } if(j==m){ cout<<i+1<<endl; cout<<"Pattern occurs start whit shift "<<i+1-m<<endl; j=next[j]; } } } int main(){ char T[]="adfgjhabcabcdaderdfgfdg"; char P[15]="hcabcdaderd"; KMP_Matcher(T,P); return 0; }
KMP的next 数组:当模式串中的某个字符跟文本串中的某个字符匹配失配时,模式串下一步应该跳到哪个位置。如模式串中在j+1处的字符跟文本串在i +1处的字符匹配失配时,下一步用next [j] +1处的字符继续跟文本串i +1处的字符匹配,相当于模式串向右移动 j - next[j] 位.
我们发现如果某个字符匹配成功,则i++、j++;如果匹配失配,i不变,模式串会跳过匹配过的next [j]个字符j=next[j]。整个算法最坏的情况是,当模式串首字符位于n-m+1的位置时才匹配成功,算法结束。
所以,如果文本串的长度为n,模式串的长度为m,那么匹配过程的时间复杂度为O(n),算上计算next的O(m)时间,KMP的整体时间复杂度为O(m + n)
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。