## FINDSR - Find String Roots

no tags

In mathematics, the N-th root of a number M, is a number K such that KN = M , i.e. KKK ... K = M where K is multiplied N times.

We can translate this into strings. In string notation, the juxtaposition is concatenation instead of multiplication. So, the N-th root of a string S is another string T such that TN = S, where T N = TTT ... T is the string T concatenated N times. For instance, if S = “abcabcabcabc”, for N = 2 the string T = “abcabc” is the N-th root of S, while for N = 4 its N-th root is T = “abc”. Note that for N = 1 any string S is the N-th root of S itself.

Given a string S you have to find the maximum N such that the N-th root of S exists. In the above example the answer would be 4, because there is no N-th root of S = “abcabcabcabc” for N > 4.

### Input

The input contains several test cases, each one described in a single line. The line contains a non-empty string S of at most 105 characters, entirely formed of digits and lowercase letters. The last line of the input contains a single asterisk (“*”) and should not be processed as a test case.

### Output

For each test case output a single line with the greatest integer N such that there exists a string T that concatenated N times is equal to S.

### Example

```Input:
abcabcabcabc
abcdefgh012
aaaaaaaaaa
*

Output:
4
1
10```

hide comments
 Anmol Pandey: 2015-01-28 14:15:09 Superb Question . try for somewhat linear O(n) avoid string STL(likely to cause TLE) Deepak Gupta: 2014-09-11 13:50:20 Was getting TLE when using memset for each case.Got AC by removing it Superty: 2014-08-21 17:07:38 Ad hoc problem. ___Durgesh___: 2014-07-19 10:03:38 interesting one :) Mitch Schwartz: 2013-10-24 15:34:16 @prudhvi: I havent experimented to find max number of test cases in an input file, but surely you can see that using only strings of random letters will tend to miss all the interesting cases for this problem? prudhvi: 2013-10-24 15:01:58 HOW MANY TEST CASES ARE THERE? FOR 1000 TEST CASES AND 10^5 SENTENCE CONTAINING RANDOM LETTERS MY PROGRAM RUNS IN 0 SEC BUT TLE HERE finally yes :) thanks Mitch Schwartz Last edit: 2013-10-25 20:00:44 Mitch Schwartz: 2013-09-12 04:12:18 @Gupta: You have expressed the notion that "getting correct answers for the sample input is a good indicator that my solution is correct". In general, the sample input/output may be quite simple, designed more for basic understanding of the problem and expected formatting rather than helping users uncover common bugs. Many people express this notion in comments, and I don't know why they do; it's completely unfounded and just takes up space. Moreover, giving additional cases in the comments is very often a spoiler, yet it is common all the same. You may try the forum for help with debugging. Gupta: 2013-09-11 16:28:03 Is there any special test case for this problem?I am getting the correct answer for the above mentioned test cases but while submitting I am getting WA.Plz comment abdou_93: 2013-06-28 12:17:58 nice @Pablo Ariel Heiber....test case very weak ..you must add cases like that.."abcababcab"..and Rejudge submission Last edit: 2013-06-28 12:28:33

 Added by: Pablo Ariel Heiber Date: 2010-08-22 Time limit: 1s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: NODEJS OBJC PERL6 VB.NET Resource: FCEyN UBA ICPC Selection 2009