此题用KMP算法做是最简单的,代码也很短。
#include<stdio.h>
#include<string.h>
char ch[1000005];
int f[1000005];
int main()
{
int i,j,k;
while(scanf("%s",ch)!=-1&&ch[0]!='.')
{
int m=strlen(ch);
for(i=1;i<m;i++)
{
j=f[i];
while(j&&ch[i]!=ch[j])j=f[j];
f[i+1]=ch[i]==ch[j]?j+1:0;
}
int tmp=m-1-(f[m]-1);//必须用f[m]-1不能直接f[m-1]
if(m%tmp==0)
printf("%d\n",m/tmp);
else
printf("1\n");
}
return 0;
}
另外附上滔神的代码,快速读入,优化到32ms
#include<stdio.h>
#include<string.h>
int next[1111111] ;
void get_next ( char *s , int n )
{
int i , j ;
j = -1 ;
next[0] = -1 ;
for ( i = 1 ; i < n ; i ++ )
{
while ( j > -1 && s[j+1] != s[i] ) j = next[j] ;
if ( s[j+1] == s[i] ) j ++ ;
next[i] = j ;
}
}
char s[1111111] ;
int main ()
{
int n , k ;
n = 0 ;
while ( s[n++] = getchar () )
{
while ( ( s[n++] = getchar () ) != 10 ) ;
n -- ;
if ( n == 1 && s[0] == '.' ) break ;
get_next ( s , n ) ;
k = next[n-1] ;
if ( n % ( n - 1 - k ) ) puts ( "1" ) ;
else printf ( "%d\n" , n / ( n - 1 - k ) ) ;
n = 0 ;
}
}
分享到:
相关推荐
#include using namespace std;...bool kmp(char *t,char *p) { int i,j; for(i=lenp,j=0;i;i++) { if(t[i]!=p[j]) return false; if(t[i]==p[j]) j++; if(j==lenp) j=0; } return true; }
北大POJ3096-Surprising Strings 解题报告+AC代码
poj 1459 Power Network.md
北大POJ初级-图算法 解题报告+AC代码
北大POJ初级-基本算法 解题报告+AC代码
POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看
poj 上的几道kmp 题的解题报告 sourse code of kmp algorithm
解决算法问题 poj1082, poj1150, poj1180, poj1201, poj1222,代码完成所给题目要求。
POJ题目分类,列出了所有的类目,里面写了一些很好的框架。
北大POJ中级-基本算法 解题报告+AC代码
北大POJ2109-Power of Cryptography 解题报告+AC代码
北大POJ1459-Power Network 解题报告+AC代码
分类很好,我自己也在做,我不是为了赚积分,只是为了分享给大家,2个积分,很便宜~
poj上的算法题目分类,对于大家想练习算法的同鞋可以参考一下,里面按类列出了各种算法的题号。
poj的代码,KMP没什么难度算法易证。
poj acm题解,包括绝大部分poj题目的题解,可以供acm爱好者学习研究
poj1087贪心算法实验报告 poj1087贪心算法实验报告
POJ中级图算法所有题目【解题报告+AC代码】 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
关于C++ 算法 北大网站POJ 八数码问题
北大POJ第1005题答案(C语言)