시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 36 18 15 78.947%

문제

라디오 방송국은 메시지를 여러 청취자에게 전송한다. 모든 청취자가 메시지를 확실히 받게 하기 위해서 메시지를 계속해서 반복 전송한다.

한 청취자가 받은 메시지가 주어진다. 항상 청취자가 받은 메시지의 길이는 방송국에서 보낸 메시지의 길이보다 크거나 같다. 이 때, 라디오 방송국에서 보낸 메시지를 구하는 프로그램을 작성하시오.

즉, 입력으로 S가 주어졌을 때, S' + S' + ... + S'를 만족하는 가장 짧은 부분수열 S'를 구하는 프로그램을 작성하시오. 

입력

첫째 줄에 S의 길이 L이 주어진다. 둘째 줄에는 길이가 L인 S가 주어진다. 메시지는 알파벳 소문자로만 이루어져 있다. (1 ≤ L ≤ 1,000,000)

출력

첫째 줄에 S'의 길이 L'을 출력한다.

예제 입력

8
cabcabca

예제 출력

3

힌트

가능한 메시지로 abc, cab, abcabc가 있다. 길이가 3보다 짧은 메시지는 없다.

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2009 P2번

  • 문제를 번역한 사람: baekjoon
  • 빠진 조건을 찾은 사람: tlwpdus