{"id":"b8b17a19-b4fc-4da3-b983-8b94ef4402fc","name":"Find String Roots","description":"In mathematics, the N-th 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.\r\nGiven a string S you have to find the maximum N such that the N-th root of S exists.\r\nFor ex :\r\nIf S= \"sumsumsumsum\", for N=2 the string T=\"sumsum\" is the N-th root of S, While for N=4 its N-th root is T= \"sum\". \r\nThe actual answer would be 4, because there is no N-th root of S=\"sumsumsumsum\" for N>4.\r\n\r\nNote that for N=1 any string S is the N-th root of itself.","inputFormat":"One line containing a non empty string S.","outputFormat":"Output a single line with the greatest integer N such that there exists a string T that concatenated N times is equal to S.","constraints":"1<= length of string <= 10^5","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main{\r\n\tpublic static void main(String[] args) throws NumberFormatException, IOException {\r\n\t\tBufferedReader br = new BufferedReader(new InputStreamReader(System.in)); \r\n\t\tString st = br.readLine();\r\n solution(st);\r\n br.readLine();\r\n\t\t\r\n\t}\r\n\r\n\r\n public static void solution(String st) {\r\n // write your code here\r\n\r\n }\r\n\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"sumsumsumsum","sampleOutput":"4","questionVideo":"https://www.youtube.com/embed/TlVeF4JfdgA","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"a2073e25-96a1-4875-b400-f40bbe2edd95","name":"Text Processing For Experts","slug":"text-processing-for-experts-859","type":0},{"id":"4d156fb0-c2a3-4503-9fee-4c666d62cc6f","name":"Find String Roots","slug":"find-string-roots","type":1}],"next":{"id":"e5a74cfe-994f-4a66-9b70-d2a5c9de4df8","name":"Manacher's Algorithm","type":1,"slug":"manacher-s-algorithm"},"prev":{"id":"0f1ba7c1-21bb-41ca-bf5f-6868b1670046","name":"Z Algorithm For Pattern Searching","type":1,"slug":"z-algorithm-for-pattern-searching"}}}

Find String Roots

In mathematics, the N-th 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. Given a string S you have to find the maximum N such that the N-th root of S exists. For ex : If S= "sumsumsumsum", for N=2 the string T="sumsum" is the N-th root of S, While for N=4 its N-th root is T= "sum". The actual answer would be 4, because there is no N-th root of S="sumsumsumsum" for N>4. Note that for N=1 any string S is the N-th root of itself.

{"id":"b8b17a19-b4fc-4da3-b983-8b94ef4402fc","name":"Find String Roots","description":"In mathematics, the N-th 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.\r\nGiven a string S you have to find the maximum N such that the N-th root of S exists.\r\nFor ex :\r\nIf S= \"sumsumsumsum\", for N=2 the string T=\"sumsum\" is the N-th root of S, While for N=4 its N-th root is T= \"sum\". \r\nThe actual answer would be 4, because there is no N-th root of S=\"sumsumsumsum\" for N>4.\r\n\r\nNote that for N=1 any string S is the N-th root of itself.","inputFormat":"One line containing a non empty string S.","outputFormat":"Output a single line with the greatest integer N such that there exists a string T that concatenated N times is equal to S.","constraints":"1<= length of string <= 10^5","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main{\r\n\tpublic static void main(String[] args) throws NumberFormatException, IOException {\r\n\t\tBufferedReader br = new BufferedReader(new InputStreamReader(System.in)); \r\n\t\tString st = br.readLine();\r\n solution(st);\r\n br.readLine();\r\n\t\t\r\n\t}\r\n\r\n\r\n public static void solution(String st) {\r\n // write your code here\r\n\r\n }\r\n\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"sumsumsumsum","sampleOutput":"4","questionVideo":"https://www.youtube.com/embed/TlVeF4JfdgA","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"a2073e25-96a1-4875-b400-f40bbe2edd95","name":"Text Processing For Experts","slug":"text-processing-for-experts-859","type":0},{"id":"4d156fb0-c2a3-4503-9fee-4c666d62cc6f","name":"Find String Roots","slug":"find-string-roots","type":1}],"next":{"id":"e5a74cfe-994f-4a66-9b70-d2a5c9de4df8","name":"Manacher's Algorithm","type":1,"slug":"manacher-s-algorithm"},"prev":{"id":"0f1ba7c1-21bb-41ca-bf5f-6868b1670046","name":"Z Algorithm For Pattern Searching","type":1,"slug":"z-algorithm-for-pattern-searching"}}}
plane

Editor


Loading...

Find String Roots

hard

In mathematics, the N-th 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. Given a string S you have to find the maximum N such that the N-th root of S exists. For ex : If S= "sumsumsumsum", for N=2 the string T="sumsum" is the N-th root of S, While for N=4 its N-th root is T= "sum". The actual answer would be 4, because there is no N-th root of S="sumsumsumsum" for N>4. Note that for N=1 any string S is the N-th root of itself.

Constraints

1<= length of string <= 10^5

Format

Input

One line containing a non empty string S.

Output

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

Sample Input

sumsumsumsum

Sample Output

4

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode