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 yuxtaposition 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 = T T T . . . 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
ssd619:
20190707 23:39:30
use Z algo ....


thekidnamedme:
20180829 18:19:46
Don't 

ambasta_4698:
20180615 11:58:07
spojtoolkit giving wrong answers for few sample inputcase 

avik26091998:
20180119 13:43:23
Similar problem  https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1239 ... Enjoy Coding 

nadstratosfer:
20170913 05:38:52
Pleased to find out that O(n) passes comfortably in Python. Comments were helpful  learn a new bit about KMP instead of wasting time on breaking open doors. 

vijay kumar paliwal:
20170725 14:11:11
Same as PERIOD !! Indeed PERIOD is generalization of this..


up79:
20170625 11:27:34
afetr 3 WA . finally AC . 

sifat_15:
20170110 08:41:24
_ Last edit: 20170116 19:20:06 

teja349:
20161228 18:57:18
is the complexity N logN??


kira28:
20161227 11:50:22
Almost the same as spoj.com/problems/PERIOD xD xD ; easy KMP

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 