首页 > 代码库 > 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;}