首页 > 其他 > 详细

循环节的问题

时间:2014-06-13 16:04:27      阅读:407      评论:0      收藏:0      [点我收藏+]

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

循环节的问题,布布扣,bubuko.com

循环节的问题

原文:http://www.cnblogs.com/yspworld/p/3784669.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!