Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
kmp算法的优化,125ms#include<stdio.h> #include<string.h> char str[1000004]; int next[1000002]; int main() { int i,j,len; while(1) { scanf("%s",str); len=strlen(str); if(len==1&&str[0]=='.') break; i=0;next[0]=-1;j=-1; while(i<len) { if(j==-1||str[i]==str[j]) { ++i;++j; if(str[i]!=str[j]) next[i]=j; else next[i]=next[j]; } else j=next[j]; } if(len%(len-next[len])==0) { printf("%d\n",len/(len-next[len])); } else printf("1\n"); } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator