A non-empty string
s is given. We need to find the largest number
k and the string
t such that
s matches the string
t given by
k times in a row.
Time limit - 1 second.
Input
Given a single string of length
N,
\(0 < N <= 10^6\), consisting only of small Latin letters.< br />
Imprint
Output one number - the largest possible
k.
Examples
| # |
Input |
Output |
| 1 |
aaaaa |
5 |
| 2 |
abcabcabc |
3 |
| 3 |
abab |
2 |