2007-04-09

JOJ ACM 1237

1237

A character string is said to have period k if it can be formed by concatenating one or more repetitions of another string of length k. For example, the string "abcabcabcabc" has period 3, since it is formed by 4 repetitions of the string "abc". It also has periods 6 (two repetitions of "abcabc") and 12 (one repetition of "abcabcabcabc").



Write a program to read a character string and determine its smallest period.

Input
A single character string of up to 80 non-blank characters.

Output
An integer denoting the smallest period of the input string.

Sample Input


HoHoHoSample Output


2代码: 
#include<stdio.h>
#include<string.h>
int main(){ 
 char str[80];
 int len,period,j; 
 while(scanf("%s",str)!=EOF) { 
    period=1;  
    len = strlen(str); 
    while(period!=len)  { 
      if(len%period!=0)   {    
         period++;    
         continue;   
      }   
      for(j=period;j<len;j++)   { 
          if(str[j]!=str[j%period])     
             break;   
      }  
     if(j==len)  {   
        printf("%d\n",period);     
        break;   
     }    
     period++;  
   }  
   if(period==len)  { 
        printf("%d\n",period);  
   } 
 } 
 return 0;
}
评论
发表评论

您还没有登录，请登录后发表评论

fuliang
搜索本博客
我的相册
53569b0e-134e-31fa-9555-bdfa6932b0e7-thumb
RSS Reader1
共 6 张
存档
最新评论