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
Nikhil Khurana: 2015-03-30 23:56:49

Dont use memset !!

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