|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초 (추가 시간 없음)||512 MB||1||1||1||100.000%|
In mathematics and computer science, the critical exponent of a string describes the largest number of times its contiguous substring is repeated in a row. The trick is that it can be a fraction. For example, the critical exponent of “Mississippi” is 7/3, as it contains the substring “ississi”, which is of length 7 and period 3.
The formal definition is as follows. Let w and x be non-empty strings. x is said to occur in w with exponent α, for positive rational α, if there is a substring y in w such as y = xnx0 where xn is x repeated n times, x0 is a prefix of x, n is the integer part of α, and the length |y| is equal to α|x|. The critical exponent of w is the maximum α over all xα that occur in w.
Given a string w, find its critical exponent.
The only line contains a string w — a sequence of lowercase English letters (1 ≤ |w| ≤ 200 000).
Output the critical exponent of w as an irreducible fraction p/q where p and q are integers without leading zeroes.