VC++2012编程演练数据结构《18》KMP算法

大灰狼

KMP算法是通过分析子串，预先计算每个位置发生不匹配的时候，所需GOTO的下一个比较位置，整理出来一个next数组，然后在上面的算法中使用。
Knuth-Morris-Pratt Algorithm，简称KMP算法。
　一种由Knuth(D.E.Knuth)、Morris(J.H.Morris）和Pratt(V.R.Pratt）三人设计的线性时间字符串匹配算法。这个算法不用计算变迁函数δ，匹配时间为Θ（n），只用到辅助函数π[1，m]，它是在Θ（m）时间内，根据模式预先计算出来的。数组π使得我们可以按需要，“现场”有效的计算（在平摊意义上来说）变迁函数δ。粗略地说，对任意状态q=0，1，…，m和任意字符a∈Σ，π[q]的值包含了与a无关但在计算δ（q，a）时需要的信息。由于数组π只有m个元素，而δ有Θ（m∣Σ∣）个值，所以通过预先计算π而不是δ，使得时间减少了一个Σ因子。[1]
　　KMP算法是通过分析子串，预先计算每个位置发生不匹配的时候，所需GOTO的下一个比较位置，整理出来一个next数组，然后在上面的算法中使用。
　当我们分析一个子串时，例如：abcabcddes. 需要分析一下，每个字符x前面最多有多少个连续的字符和字符串从初始位置开始的字符匹配。然后+1就行了（别忘了，我们的字符串都是从索引1开始的）当然，不要相同位置自己匹配，默认第一个字符的匹配数是0。
　设字符串为 x1x2x3...xn，其中x1，x2，x3，... xi，... xn均是字符，设ai为字符xi对应的整数。则a=m，当且仅当满足如下条件：字符串x1x2...xm equals 字符串x(i-m+1）...xi-1 xi 并且x1x2...xm x(m+1） unequals x(i-m) x(i-m+1）...xi-1 xi。
　abcabcddes
　　0111234111
　　|----------------------默认是0
　　--| | |-----------------不能自己在相同位置进行字符匹配，所以这里认为没有匹配字符串，所以0+1 =1，继续从1开始匹配
　　------| | |-----------前面的字符和开始位置的字符相同，所以是2,3,4
　　-----------| | | |-------不匹配只能取1。

　　希望能明白的是，如果开始字符是 Ch1的话，那么我们就是要在串中第2个Ch1后面的位置开始自己和自己匹配，计算最大的吻合度。

打开IDE

我们创建一个工程

KMP实现如下

[cpp] view plaincopy

• /字符串的模式匹配  
• #include<iostream>  
• #include<iomanip>  
• #include<stdio.h>  
• #include<stdlib.h>  
• #include<string.h>  
• #define MAXSTRLEN 64  
• using namespace std;  
• void GetNext(char T[MAXSTRLEN],int (&next)[64])  
• {int i,j;i=1;next[1]=j=0;  
• while(i<(int)T[0])  
• if(j==0||T==T[j])  
•   {++i;++j;next=j;}  
• else j=next[j];  
• for(j=1;j<(int)T[0];j++)  
• {printf("next[%d]=%-3d",j,next[j]);  
•   if((j)%5==0) printf("\n");}  
• cout<<endl;   
• }  
• void GetNext(char T[MAXSTRLEN],int (&next)[64],int m)  
• {int i,j;i=0;next[0]=-1;  
• for(j=1;j<m;j++)  
• {i=next[j-1];  
• while(T[j]!=T[i+1]&&i>=0) i=next;  
• if(T[j]==T[i+1]) next[j]=i+1;  
• else next[j]=-1;}  
• for(j=0;j<=m;j++)  
•   {printf("next[%d]=%-3d",j,next[j]);  
•    if((j+1)%5==0) printf("\n");}  
• cout<<endl;  
• }  
• void GetNextVal(char T[MAXSTRLEN],int (&next)[64])  
• {int i,j;i=1;next[1]=j=0;  
• while(i<(int)T[0])  
• if(j==0||T==T[j])  
•   {++i;++j;  
•    if(T!=T[j]) next=j;  
•    else next=next[j];}  
•   else j=next[j];  
• for(i=1;i<(int)T[0];i++)  
•   {printf("next[%d]=%-3d",i,next);  
•    if(i%5==0) cout<<endl;}  
• cout<<endl;   
• }  
• int IndexKMP(char S[MAXSTRLEN],char T[MAXSTRLEN],int (&next)[64])  
• {int i,j,n,m;i=j=1;  
• n=(int)S[0];m=(int)T[0];  
• while((i<n||j<m)&&T[j]!='\0'&&S!='\0')  
•   if(j==0||S==T[j]) {++i;++j;}  
•   else j=next[j];  
• if(j>=m) return i+1-m;  
• else return 0;  
• }  
• int IndexKMP(char S[MAXSTRLEN],char T[MAXSTRLEN],int (&next)[64],int pos)  
• {int i,j;i=pos;j=1;  
• while((i<(int)S[0]||j<(int)T[0])&&T[j]!='\0'&&S!='\0')  
•   if(j==0||S==T[j]) {++i;++j;}  
•   else j=next[j];  
• if(j>=(int)T[0]) return i+1-(int)T[0];  
• else return 0;  
• }  
• int IndexKMP(char S[MAXSTRLEN],char T[MAXSTRLEN],int (&next)[64],int n,int m)  
• {int i,j;i=j=0;  
• while(i<n&&j<m)  
•   if(S==T[j]) {++i;++j;}  
•   else if(j==0) i++;  
•        else j=next[j-1]+1;  
• if(j<m) return -1;  
• else return i-m+1;  
• }  
• int IndexBF(char S[MAXSTRLEN],char T[MAXSTRLEN],int pos)  
• {int i,j;i=pos;j=1;  
• while(i<=S[0]&&j<=T[0])  
•   if(S==T[j]) {++i;++j;}  
•   else {i=i-j+2;j=1;}  
• if(j>T[0]) return i-T[0];  
• else return 0;  
• }  
  

调用如下

[cpp] view plaincopy

• void main()  
• {printf("Findstr.cpp运行结果:\n");  
• int Index,N,M,next[64]={0};  
• char s[MAXSTRLEN],t[MAXSTRLEN];  
• printf("GetNext-IndexKMP的结果:\n");  
• printf("输入主串s:");gets(s);  
• printf("输入模式串t:");gets(t);  
• N=strlen(s);M=strlen(t);  
• printf("主串s长=%d\n",N);  
• printf(" 模式串t长=%d\n",M);  
• GetNext(t,next,M);  
• Index=IndexKMP(s,t,next,N,M);  
• if(Index!=-1)  
•   printf("模式串在主串的位置从第%d个字符开始\n",Index);  
• else printf("主串s中不含模式串t\n");  
•   
• printf("GetNext-IndexKMP的结果:\n");  
• s[0]=N;t[0]=M;  
• GetNext(t,next);  
• Index=IndexKMP(s,t,next,1);  
• if(Index)  
•   printf("模式串在主串的位置从第%d个字符开始\n",Index);  
• else printf("主串s中不含模式串t\n");  
•   
• printf("GetNextVal-IndexKMP的结果:\n");  
• GetNextVal(t,next);  
• Index=IndexKMP(s,t,next,1);  
• if(Index)  
•   printf("模式串在主串的位置从第%d个字符开始\n",Index);  
• else printf("主串s中不含模式串t\n");  
•   
• printf("GetNext-IndexKMP的结果:\n");  
• GetNext(t,next);  
• Index=IndexKMP(s,t,next);  
• if(Index)  
•    printf("模式串t在主串s中的位置从第%d个字符开始\n",Index);  
• else printf("主串s中不含模式串t\n");  
•    
• printf("IndexBF的结果:\n");  
• Index=IndexBF(s,t,1);  
• if(Index)  
•    printf("模式串t在主串s中的位置从第%d个字符开始\n",Index);  
• else printf("主串s中不含模式串t\n");  
• cin.get();}  
  

效果如下