FINDSR - Find String Roots

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

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

hide comments
2016-12-27 11:50:22
Almost the same as spoj.com/problems/PERIOD xD xD ; easy KMP
AC in one go!!!!
2016-12-22 20:54:16
3 Sigsegv for taking a small array..:(..Simple adhoc.
2016-10-29 11:05:12
Simple adhoc!
2016-08-19 10:45:27
Learn something new about KMP. thank you, author
2016-01-23 17:14:43 Liquid_Science
after 2 wa ,learnt something ,worth it.
2015-12-11 08:01:11 xxbloodysantaxx
I do not know , I used vectors and strings . My complexity is O(N* LOG N ) then too my code runs perfectly .
Morover it took only 0.02 seconds to run !!

I think the complexity is lesser than O (N*LOGN) now as I am only considering i which are a divisors of N whose density is quite low ! Hence the summation also drops.

I did it with O(N) solution too same running time !!

Last edit: 2015-12-11 09:04:02
2015-10-06 16:12:25 THESEUS
Getting constant TLE !!!! Plz help :(
Code at <snip>

Last edit: 2022-09-18 16:01:11
2015-06-02 18:14:16 :.Mohib.:
Easy... :)
2015-06-01 17:11:47 i_am_looser
easy kmp... ;)
2015-04-26 17:02:21 Sunil
try repeats as well
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.