시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 (추가 시간 없음) | 512 MB | 48 | 17 | 12 | 36.364% |
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.
mississippi
7/3
abab
2/1