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.


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.


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.




hide comments
Vitalis Salis: 2013-04-07 13:45:42

I didn't use any string algorithm, yet got accepted. I could say it is an ad hoc problem.

Raghavendran Ramachandran: 2012-10-04 13:04:58

Shubham.IIITM: 2012-08-28 18:36:30

----Removed After AC----
Wow Accepted!!! A good question seriously :)

Last edit: 2012-08-28 19:08:00
:): 2012-06-23 14:07:50

plz give hint ...

Grandmaster: 2012-05-17 03:30:41

wow.. cant believe the way it got accepted :P .. a new lesson learned.

Last edit: 2012-05-17 03:36:44
Michael T: 2010-10-29 05:26:33

I guess some string algorithm would be needed then.)

Last edit: 2010-10-29 05:27:26
numerix: 2010-10-26 21:15:14

You can even get it AC with a pure Python solution (without psyco) ...

Michael T: 2010-10-24 05:25:31

Indeed. Even in python (psyco req though).

Last edit: 2010-10-24 05:28:24

Added by:Pablo Ariel Heiber
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