Smallest Repeating Unit
mediumStrings II+20 XPTime limit 2s
Some strings are just a shorter block written several times: abcabcabc is abc three times, and abab is ab twice. Find the length of the shortest block that, repeated a whole number of times, gives exactly the string. If no shorter block works, the answer is the length of the string itself.
Input: one line with a string of lowercase letters.
Output: the length of the smallest repeating unit.
Constraints: 1 ≤ length ≤ 10⁵.
Think about it: checking every divisor of n works but can be slow. With the prefix function, let p = n − pi[n−1] (pi[n−1] is the longest proper prefix that is also a suffix). If p divides n, the string is a repetition of its first p characters; otherwise it doesn't repeat at all.
Sample input 1
abcabcabc
Sample output 1
3
Sample input 2
abcab
Sample output 2
5
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).