POJ 2752 C++ （KMP）

#include

#include

using namespace std;

int n,next[400008],result[400008];;

char s[400008],t[400008];

void Get_next()

{int j,k;

j=1;

k=0;

next[1]=0;

while(j<=n+1)

　　　 { if(k==0 || s[j]==s[k])

　　　　　　{ j++;

　　　　　　　k++;

　　　　　　　next[j]=k;

　　　　　　 }

　　　　　else

　　　　　　 k=next[k];

　　　　 }

}

int main()

{ int i,k;

　 freopen("in.txt","r",stdin);

　 freopen("out.txt","w",stdout);

　 while(scanf("%s",t)!=EOF)

　　　　 {n=strlen(t);

　　　　　for(i=1;i<=n;i++)

　　　　　　　　s[i]=t[i-1];

　　　　　 s[i]='#';

　　　　　 Get_next();

　　　　　 k=0;

　　　　　 result[k++]=n+1;

　　　　　 i=n+1;

　　　　　 while(i!=1)

　　　　　　　　{ if(next[i]!=1)

　　　　　　　　　　 result[k++]=next[i];

　　　　　　　　　i=next[i];

　　　　　　　　 }

　　　　　for(i=k-1;i>0;i--)

　　　　　　　printf("%d ",result[i]-1);

　　　　 printf("%dn",result[i]-1);　　　　　　　　　　

　　 }

　 return 0;

}