FINDSR  Find String Roots
In mathematics, the Nth root of a number M, is a number K such that K^{N} = 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 Nth root of a string S is another string T such that T^{N} = 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 Nth root of S, while for N = 4 its Nth root is T = “abc”. Note that for N = 1 any string S is the Nth root of S itself.
Given a string S you have to find the maximum N such that the Nth root of S exists. In the above example the answer would be 4, because there is no Nth 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 nonempty string S of at most 10^{5} 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
kira28:
20161227 11:50:22
Almost the same as spoj.com/problems/PERIOD xD xD ; easy KMP


sas1905:
20161222 20:54:16
3 Sigsegv for taking a small array..:(..Simple adhoc. 

siddharth_0196:
20161029 11:05:12
Simple adhoc! 

sieunhanbom04:
20160819 10:45:27
Learn something new about KMP. thank you, author 

Liquid_Science:
20160123 17:14:43
after 2 wa ,learnt something ,worth it. 

xxbloodysantaxx:
20151211 08:01:11
I do not know , I used vectors and strings . My complexity is O(N* LOG N ) then too my code runs perfectly .


THESEUS:
20151006 16:12:25
Getting constant TLE !!!! Plz help :(


:.Mohib.::
20150602 18:14:16
Easy... :) 

i_am_looser:
20150601 17:11:47
easy kmp... ;) 

Sunil:
20150426 17:02:21
try repeats as well

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