KMP概述
KMP算法,是一种对暴力单模式字符串匹配的改进算法,他可以在O(M+N)的时间内求出在文本串中模式串的出现次数和位置,具体实现利用了字符串的自匹配性,从而减少了一些不必要的比较没降低了复杂度。
原理:
/*kmp算法,最优复杂度为0(m+n), kmp算法比传统的暴力算法的优势在于 用模串自身的匹配信息来减少不必要的 匹配,*/ #include<cstdio> #include<cstring> #include<iostream> #include<string> #include<algorithm> using namespace std; char p[1010]; char t[1010]; int Next[1010]; void getNext(char p[]) { int len=strlen(p); int k=0; //k为当前匹配长度 Next[0]=0; for(int i=1;i<len;i++) { while(k&&p[i]!=p[k]) //当前匹配长度不为0且当前位实配时,需要在已匹配串中找子串,可以看做对模式串kmp,这也是为什么求next数组和kmp代码看起来一样的原因。 k=Next[k-1]; if(p[i]==p[k]) k++; //递归求next数组 Next[i]=k; } return ; } int kmp(char p[],char t[]) { int lenp=strlen(p); int lent=strlen(t); int k=0,cnt=0; for(int i=0;i<lent;i++) { while(k&&p[k]!=t[i]) k=Next[k-1]; if(t[i]==p[k]) k++; if(k==lenp) { cnt++; k=0; //当匹配不可覆盖时,即每个点只能用一次,可覆盖时,next=next[i-1]; } } return cnt; } int main() { while(~scanf("%s%s",t,p)&&t[0]!='#') { getNext(p); // for(int i=1;i<strlen(p);i++) // cout<<next[i]<<" "; printf("%d\n",kmp(p,t)); } return 0; }
沙发