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)

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。