pku 2406 - wyiu - C++博客

传说可以用kmp的精髓next[]来做，但是怎么都领悟不了，所以就凭感觉直接模拟了
因为s=a^n
取前缀，分别从长度1到strlen，然后与后面剩下的比较，如果ok就说明这个长度是a的最短的长度，然后sterlen(s)/strlen(a)

#include<iostream>

using namespace std;

#define M 1000000

char t[M+1],p[M+1];

int lent,lenp;

bool kmp(char *t,char *p)

{

int i,j;

for(i=lenp,j=0;i<lent;i++)

{

if(t[i]!=p[j]) return false;

if(t[i]==p[j]) j++;

if(j==lenp) j=0;

}

return true;

}

int main()

{

int i;

while(scanf(" %s",&t)!=EOF && t[0]!='.')

{

lent=strlen(t);

for(i=0;i<lent;i++)

{

p[i]=t[i];

p[i+1]='\0';

lenp=i+1;

if(lent%lenp==0 && kmp(t,p))

{

printf("%d\n",lent/lenp);

break;

}

return 0;

}

posted on 2009-08-03 14:25 wyiu 阅读(279) 评论(0) 编辑收藏引用所属分类: POJ

只有注册用户登录后才能发表评论。
【推荐】100%开源！大型工业跨平台软件C++源码提供，建模，组态！

相关文章: poj 1061 线性同余 poj 2115 线性同余 poj 3368 rmq(st) poj 3264 RMQ poj 2352 树状数组 poj 1469 二分匹配 poj 2186 有向图强连通分支 poj 2239 二分图最大匹配 poj 3748 位运算 poj 2724 二分匹配

网站导航: 博客园 IT新闻 BlogJava 知识库博问管理

随笔分类(84)