프로그램 명: boi_radio
제한시간: 1 초

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 received by one of the recipients. It is known the sequence is at least as long as the message.

Your task is to write a program that extracts the message transmitted by the station. More formally, your program needs to find the shortest subsequence S′ of the input sequence S such that S in turn is a subsequence of the (sufficiently long) repetition S′ + S′ + ··· + S′.

입력

The input is read from standard input. The first line contains a single integer L, the length of the sequence S. The second line contains exactly L characters, the sequence S itself. The sequence consists of lowercase letters (a . . . z).

출력

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.

입출력 예

입력

8
cabcabca

출력

3
The message could be abc, cab or abcabc, but there’s no possible message shorter than 3 characters.

Constraints

1 < L ≤ 1,000,000. 
출처: boi 2009 practice
[질/답] [제출 현황] [푼 후(0)]
[ 채 점 ] [홈으로]  [뒤 로]