10322: CF EDU - Suffix Array - Step 5 - F. Periodic Substring
[Creator : ]
Description
Given the string $s$. Find a maximum integer $k$ such that there is a non-empty substring in the string $s$ that is a concatenation of $k$ equal strings.
Input
The first line of input contains the string $s\ (1≤|s|≤400,000)$. The string consists of lowercase English letters.
Output
Print the desired value $k$.
Sample 1 Input
aabaaabaaabaaabaab
Sample 1 Output
4
Sample 2 Input
aabaabb
Sample 2 Output
2
Sample 3 Input
aaaa
Sample 3 Output
4
ppppplppp
5
Sample 4 Input
nn
Sample 4 Output
2