首页 > 代码库 > poj 2752 Seek the Name, Seek the Fame(kmp)

poj 2752 Seek the Name, Seek the Fame(kmp)

注意细节边界的时候 容易忽略错误 在除给定的例子之外 想一个特殊符合题意的特殊例子。

#include<iostream>#include<cstdio>#include<cstring>using namespace std;void GetFail(int *f,char* P){    int m=strlen(P);    f[0]=f[1]=0;    for(int i=1;i<=m;i++)    {        int j=f[i];        while(j&&P[i]!=P[j]) j=f[j];        f[i+1]= P[i]==P[j]?j+1:0;    }}char str[400005];int f[400005];int h[400005],cnt;int main(void){    while(cin>>str)    {        cnt=0;        memset(f,0,sizeof(f));        memset(h,0,sizeof(h));        GetFail(f,str);        int m=strlen(str);        int j=m;        do        {            h[cnt++]=j;            j=f[j];        }while(f[j]);        if(j!=0) h[cnt++]=j;        for(j=cnt-1;j>0;j--)        {            cout<<h[j]<<" ";        }        cout<<h[0]<<endl;    }    return 0;}

 

poj 2752 Seek the Name, Seek the Fame(kmp)