首页 > 代码库 > 循环节的问题
循环节的问题
SDUT 循环节
Time Limit: 1000ms Memory limit: 65536K 有疑问?点这里^_^
题目描述
X最近爱上了一种奇怪的游戏,就是找出一个字符串中的最小循环节。
对于最小循环节的定义:对于字符串A存在字串B,使得A是由N个完整的B组成的,那么B就是A的一个循环节,长度最小的那一个为最小循环节。
输入
多组输入。
每组输入一个字符串,长度不大于80,只包含26个小写字母。
输出
输出一个字符串,代表最小循环节。
示例输入
aaaa abab
示例输出
a ab输入一个字符串,找到次字符串的最小循环节,并把它输出出来!
在我开始做的时候,曾经拥的是几个i, j的指针指了指,然后输出,做错了,
后来学了数据结构,我又用了KMP的算法高了一次,然后超时了,超时可想而知是为什么!
再后来从《算法竞赛 经典入门》的书中发现 刘汝佳 还有一种做法,不仅代码简短,可读性也强! 十分厉害啊!
code as followed:
#include <stdio.h>
#include <string.h>
int main()
{
char s[100];
int len;
while(scanf("%s", s)!=EOF)
{
len = strlen(s);
for(int i=1; i<=len; i++)
if(len%i==0)
{
{
int ok = 1;
for(int j=i; j<len; j++)
{
if( s[j] != s[j%i] )
{
ok = 0;
break;
}
}
if(ok!=0)
{
printf("%d\n", i);
for(int k=0; k<i; k++)
{
printf("%c", s[k] );
}
printf("\n");
break;
}
}
}
}
return 0;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。