Write a program in C/C++ to read a character string and determine its smallest period.?

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


HoHoHo


Sample Output


2

Write a program in C/C++ to read a character string and determine its smallest period.?
Do your homework yourself or quit school and never take programming again.
Reply:I think the algorithm is easy if you know pointers. Maybe this gives you an idea, it's not the best implementation but may work:





int GetPeriod(char*str)


{


int period=strlen(str);


for(int i=1;i%26lt;strlen(str);i++)


{


char copy[81];


memset(copy,0,sizeof(copy));


strncpy(copy,str,i);


char *ptr=str;


int count=0;


while(ptr)


{


if(strstr(ptr,copy)!=ptr)break;


ptr=strstr(ptr,copy);


if(ptr)


{


ptr+=strlen(copy);


if(strlen(ptr)==strlen(copy))


{


if(!strcmp(copy,ptr))


period=strlen(copy);


}


}


};


}


return period;


}
Reply:A person is said to be a slacker if he/she posts homework questions on Yahoo! Answers.





Anyway, you need dynamic programming: http://en.wikipedia.org/wiki/Dynamic_Pro...





Look, string abcabc. How do you find its period?





Wouldn't be easier to find the period of abc and abc separately, and if they are each the same, then we know that abcabc has the same period?





Use recursion:





a bcabcabcabc has periods of 1 and 11. No good.


ab cabcabcabc has periods of 2 and 10. No good.


abc abcabcabc has periods of 3 and 3. DING DING DING.





But how do you find periods for something like bcabcabcabc? Same way as above. That's the recursive part.





One gotcha: abcdef, if you split into abc and def, will have matching periods, but you must check to make sure the two strings are the same.