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
slothsphereoj: 2024-03-12 08:35:08

No standard algo required for me, but this question leaves a huge room for thinking and experimentation with different ideas.

Thoughts as of 12 March 2024: People nowadays always said A.I. can replace all professions that requires higher cognitive abilities, but I would never see this as the reason to disrespect programming and maths. Codes and formulas are rigid rules but the implications and ideas behind them is a higher form of artistic expressions on the ways to handle problems and riddles.

I do not understand why some "humans" (or must I say, non-humans) can come up with insightful questions and ideas while others simply, regretfully, "cannot", given that humans shall have similar genetic make-ups.

ssd619: 2019-07-07 23:39:30

use Z algo ....

thekidnamedme: 2018-08-29 18:19:46


ambasta_4698: 2018-06-15 11:58:07

spojtoolkit giving wrong answers for few sample inputcase

avik26091998: 2018-01-19 13:43:23

Similar problem - ... Enjoy Coding

nadstratosfer: 2017-09-13 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: 2017-07-25 14:11:11

Same as PERIOD !! Indeed PERIOD is generalization of this..

up79: 2017-06-25 11:27:34

afetr 3 WA . finally AC .

sifat_15: 2017-01-10 08:41:24


Last edit: 2017-01-16 19:20:06
teja349: 2016-12-28 18:57:18

is the complexity N logN??

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