Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

kmp算法的优化,125ms

Posted by B10330224 at 2011-05-19 16:47:27 on Problem 2406
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator