Hide

Problem F
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

Please log in to submit a solution to this problem

Log in