Radio Transmission

Interview

Time limit1sMemory limit128 MB

Summary

Given a received string that is part of a repeated broadcast, find the length of the shortest repeating unit using KMP failure function.

Level: Medium4 of 10
Topics: String matching, String
Solved: No attempts yet

Problem

A radio station transmits a single message to many listeners. To make sure every listener receives it, the station broadcasts the same message over and over, concatenating it end to end without stopping.

You are given a string S that one listener received. The length of the received string is always greater than or equal to the length of the original message the station actually sent. Write a program that recovers the original message.

Formally, given a string S, find the shortest string S′ such that S is a substring of S′ + S′ + ⋯ + S′ (S′ repeated some number of times), and output the length of that S′.

Input

The first line contains the length L of S. The second line contains the string S of length L. S consists only of lowercase letters. (1 ≤ L ≤ 1,000,000)

Output

Print the length L′ of the shortest original message S′.

Hint

For example, if S is cabcabca, possible original messages include cab, abc, and abcabc, and no message shorter than length 3 exists. Therefore the answer is 3.

Examples4

Example 1
Input
```
8
cabcabca
```
Expected output
```
3
```
Example 2
Input
```
1
a
```
Expected output
```
1
```
Example 3
Input
```
5
aaaaa
```
Expected output
```
1
```
Example 4
Input
```
4
abcd
```
Expected output
```
4
```