| ||||||||||
| 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