Problem D
Radio Transmission
A radio station needs to transmit a message to several recipients. To ensure all listeners get it, the message is played again and again in a continuous loop.
You’re given a sequence of characters recieved by one of the recipients. It is known that the sequence is at least as long as the message.
Your task is to write a program the extracts the message transmitted by the station. More formally, your program needs to find the shortest subsring $S’$ of the input string $S$ such that $S$ in turn is a substring of the (sufficiently long) repetition $S’ + S’ + \ldots + S’$.
Input
The first line contains a single integer $1 \le L \le 1\, 000\, 000$, the length of the string $S$. The second line contains exactly $L$ characters, the string $S$ itself. The sequence consists of lowercase letters a-z.
Output
The program should write one line to standard output containing a single integer: the length $L’$ of the message $S’$. Note that $L’$ must be the smallest possible. If there are multiple smallest $L’$, you may output any of them.
Explanation of Sample 1
The message could (among other options) be “abc”, “cab” or “abcabc”, but there is no possible message shorter than $3$ characters.
| Sample Input 1 | Sample Output 1 |
|---|---|
8 cabcabca |
3 |
