시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 73 33 28 59.574%

문제

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

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

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

입력

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

출력

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

예제 입력 1

8
cabcabca

예제 출력 1

3

힌트

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

W3sicHJvYmxlbV9pZCI6IjMzNTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI3N2NcdWI1MTRcdWM2MjQgXHVjODA0XHVjMWExIiwiZGVzY3JpcHRpb24iOiI8cD5cdWI3N2NcdWI1MTRcdWM2MjQgXHViYzI5XHVjMWExXHVhZDZkXHVjNzQwIFx1YmE1NFx1YzJkY1x1YzljMFx1Yjk3YyBcdWM1ZWNcdWI3ZWMgXHVjY2FkXHVjZGU4XHVjNzkwXHVjNWQwXHVhYzhjIFx1YzgwNFx1YzFhMVx1ZDU1Y1x1YjJlNC4gXHViYWE4XHViNGUwIFx1Y2NhZFx1Y2RlOFx1Yzc5MFx1YWMwMCBcdWJhNTRcdWMyZGNcdWM5YzBcdWI5N2MgXHVkNjU1XHVjMmU0XHVkNzg4IFx1YmMxYlx1YWM4YyBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YmE1NFx1YzJkY1x1YzljMFx1Yjk3YyBcdWFjYzRcdWMxOGRcdWQ1NzRcdWMxMWMgXHViYzE4XHViY2Y1IFx1YzgwNFx1YzFhMVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTVjIFx1Y2NhZFx1Y2RlOFx1Yzc5MFx1YWMwMCBcdWJjMWJcdWM3NDAgXHViYTU0XHVjMmRjXHVjOWMwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVkNTZkXHVjMGMxIFx1Y2NhZFx1Y2RlOFx1Yzc5MFx1YWMwMCBcdWJjMWJcdWM3NDAgXHViYTU0XHVjMmRjXHVjOWMwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCBcdWJjMjlcdWMxYTFcdWFkNmRcdWM1ZDBcdWMxMWMgXHViY2Y0XHViMGI4IFx1YmE1NFx1YzJkY1x1YzljMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWI3N2NcdWI1MTRcdWM2MjQgXHViYzI5XHVjMWExXHVhZDZkXHVjNWQwXHVjMTFjIFx1YmNmNFx1YjBiOCBcdWJhNTRcdWMyZGNcdWM5YzBcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlx1Yzk4OSwgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgUyYjMzk7ICsgUyYjMzk7ICsgLi4uICsgUyYjMzk7XHViOTdjIFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVjOWU3XHVjNzQwIFx1YmQ4MFx1YmQ4NFx1YzIxOFx1YzVmNCBTJiMzOTtcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFNcdWM3NTggXHVhZTM4XHVjNzc0IExcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWUzOFx1Yzc3NFx1YWMwMCBMXHVjNzc4IFNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJhNTRcdWMyZGNcdWM5YzBcdWIyOTQgXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiAoMSAmbGU7IEwgJmxlOyZuYnNwOzEsMDAwLDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFMmIzM5O1x1Yzc1OCBcdWFlMzhcdWM3NzQgTCYjMzk7XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVhYzAwXHViMmE1XHVkNTVjIFx1YmE1NFx1YzJkY1x1YzljMFx1Yjg1YyBhYmMsIGNhYiwgYWJjYWJjXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVhZTM4XHVjNzc0XHVhYzAwIDNcdWJjZjRcdWIyZTQgXHVjOWU3XHVjNzQwIFx1YmE1NFx1YzJkY1x1YzljMFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMzU2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUmFkaW8gVHJhbnNtaXNzaW9uIiwiZGVzY3JpcHRpb24iOiI8cD5BIHJhZGlvIHN0YXRpb24gbmVlZHMgdG8gdHJhbnNtaXQgYSBtZXNzYWdlIHRvIHNldmVyYWwgcmVjaXBpZW50cy4gVG8gZW5zdXJlIGFsbCBsaXN0ZW5lcnMgZ2V0IGl0LCB0aGUgbWVzc2FnZSBpcyBwbGF5ZWQgYWdhaW4gYW5kIGFnYWluIGluIGEgY29udGludW91cyBsb29wLjxcL3A+XHJcblxyXG48cD5Zb3UmcnNxdW87cmUgZ2l2ZW4gYSBzZXF1ZW5jZSBvZiBjaGFyYWN0ZXJzIHJlY2VpdmVkIGJ5IG9uZSBvZiB0aGUgcmVjaXBpZW50cy4gSXQgaXMga25vd24gdGhlIHNlcXVlbmNlIGlzIGF0IGxlYXN0IGFzIGxvbmcgYXMgdGhlIG1lc3NhZ2UuPFwvcD5cclxuXHJcbjxwPllvdXIgdGFzayBpcyB0byB3cml0ZSBhIHByb2dyYW0gdGhhdCBleHRyYWN0cyB0aGUgbWVzc2FnZSB0cmFuc21pdHRlZCBieSB0aGUgc3RhdGlvbi4gTW9yZSBmb3JtYWxseSwgeW91ciBwcm9ncmFtIG5lZWRzIHRvIFx1ZmIwMW5kIHRoZSBzaG9ydGVzdCBzdWJzZXF1ZW5jZSBTJnByaW1lOyBvZiB0aGUgaW5wdXQgc2VxdWVuY2UgUyBzdWNoIHRoYXQgUyBpbiB0dXJuIGlzIGEgc3Vic2VxdWVuY2Ugb2YgdGhlIChzdWZcdWZiMDFjaWVudGx5IGxvbmcpIHJlcGV0aXRpb24gUyZwcmltZTsgKyBTJnByaW1lOyArICZtaWRkb3Q7Jm1pZGRvdDsmbWlkZG90OyArIFMmcHJpbWU7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgaXMgcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0LiBUaGUgXHVmYjAxcnN0IGxpbmUgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciBMLCB0aGUgbGVuZ3RoIG9mIHRoZSBzZXF1ZW5jZSBTLiBUaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgZXhhY3RseSBMIGNoYXJhY3RlcnMsIHRoZSBzZXF1ZW5jZSBTIGl0c2VsZi4gVGhlIHNlcXVlbmNlIGNvbnNpc3RzIG9mIGxvd2VyY2FzZSBsZXR0ZXJzIChhLi4ueikuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIHByb2dyYW0gc2hvdWxkIHdyaXRlIG9uZSBsaW5lIHRvIHN0YW5kYXJkIG91dHB1dCBjb250YWluaW5nIGEgc2luZ2xlIGludGVnZXI6IHRoZSBsZW5ndGggTCZwcmltZTsgb2YgdGhlIG1lc3NhZ2UgUyZwcmltZTsuIE5vdGUgdGhhdCBMJnByaW1lOyBtdXN0IGJlIHRoZSBzbWFsbGVzdCBwb3NzaWJsZS48XC9wPlxyXG4iLCJoaW50IjoiPHA+aGUgbWVzc2FnZSBjb3VsZCBiZSBhYmMsIGNhYiBvciBhYmNhYmMsIGJ1dCB0aGVyZSZyc3F1bztzIG5vIHBvc3NpYmxlIG1lc3NhZ2Ugc2hvcnRlciB0aGFuIDMgY2hhcmFjdGVycy48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2009 P2번

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