Skills101
← All coding problems

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).

Loading editor…

Log in to run and submit your code — it's free.