首页 > 代码库 > KMP算法代码
KMP算法代码
#include<stdio.h>#include<string.h>class KMP{public: KMP(const char *P,const char *Q); void Deal();private: void GenPi(); void Search(); char q[1024]; char p[1024]; int pi[1024]; int Result[1024];};KMP::KMP(const char *P,const char *Q){ strcpy(p,P); strcpy(q,Q);}void KMP::GenPi(){ int i,len,k; k=0; len = strlen(q); pi[0]=0; for(int i=1;i<len;i++) { while(k>0 && q[k]!=q[i]) //k代表的是前面匹配上的个数,由于数组从0开始,因此k用在[]中时,需要减1 { k = pi[k-1]; } if(q[k]==q[i]) { k++; } pi[i]=k; }}void KMP::Search(){ int i,j,len,k,m; m = strlen(q); k=0; j=0; len = strlen(p); for(int i=0;i<len;i++) { while(k>0 && q[k]!=p[i]) { k=pi[k-1]; } if(q[k] == p[i]) { k++; } if(k == m) { printf("%d\n",i); k = pi[k-1]; } }}void KMP::Deal(){ GenPi(); Search();}int main(){ char *P="fffff"; char *Q="fff"; KMP oKMP(P,Q); oKMP.Deal(); return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。