시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 59 29 24 72.727%

문제

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

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

즉, 입력으로 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+XHVkNTVjIFx1Y2NhZFx1Y2RlOFx1Yzc5MFx1YWMwMCBcdWJjMWJcdWM3NDAgXHViYTU0XHVjMmRjXHVjOWMwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVkNTZkXHVjMGMxIFx1Y2NhZFx1Y2RlOFx1Yzc5MFx1YWMwMCBcdWJjMWJcdWM3NDAgXHViYTU0XHVjMmRjXHVjOWMwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCBcdWJjMjlcdWMxYTFcdWFkNmRcdWM1ZDBcdWMxMWMgXHViY2Y0XHViMGI4IFx1YmE1NFx1YzJkY1x1YzljMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNC4gXHVjNzc0IFx1YjU0YywgXHViNzdjXHViNTE0XHVjNjI0IFx1YmMyOVx1YzFhMVx1YWQ2ZFx1YzVkMFx1YzExYyBcdWJjZjRcdWIwYjggXHViYTU0XHVjMmRjXHVjOWMwXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cdWM5ODksIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBTXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFMmIzM5OyArIFMmIzM5OyArIC4uLiArIFMmIzM5O1x1Yjk3YyBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YzllN1x1Yzc0MCBcdWJkODBcdWJkODRcdWMyMThcdWM1ZjQgUyYjMzk7XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBTXHVjNzU4IFx1YWUzOFx1Yzc3NCBMXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFlMzhcdWM3NzRcdWFjMDAgTFx1Yzc3OCBTXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViYTU0XHVjMmRjXHVjOWMwXHViMjk0IFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWMxOGNcdWJiMzhcdWM3OTBcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gKDEgJmxlOyBMICZsZTsmbmJzcDsxLDAwMCwwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBTJiMzOTtcdWM3NTggXHVhZTM4XHVjNzc0IEwmIzM5O1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YWMwMFx1YjJhNVx1ZDU1YyBcdWJhNTRcdWMyZGNcdWM5YzBcdWI4NWMgYWJjLCBjYWIsIGFiY2FiY1x1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YWUzOFx1Yzc3NFx1YWMwMCAzXHViY2Y0XHViMmU0IFx1YzllN1x1Yzc0MCBcdWJhNTRcdWMyZGNcdWM5YzBcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzM1NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlJhZGlvIFRyYW5zbWlzc2lvbiIsImRlc2NyaXB0aW9uIjoiPHA+QSByYWRpbyBzdGF0aW9uIG5lZWRzIHRvIHRyYW5zbWl0IGEgbWVzc2FnZSB0byBzZXZlcmFsIHJlY2lwaWVudHMuIFRvIGVuc3VyZSBhbGwgbGlzdGVuZXJzIGdldCBpdCwgdGhlIG1lc3NhZ2UgaXMgcGxheWVkIGFnYWluIGFuZCBhZ2FpbiBpbiBhIGNvbnRpbnVvdXMgbG9vcC48XC9wPlxyXG5cclxuPHA+WW91JnJzcXVvO3JlIGdpdmVuIGEgc2VxdWVuY2Ugb2YgY2hhcmFjdGVycyByZWNlaXZlZCBieSBvbmUgb2YgdGhlIHJlY2lwaWVudHMuIEl0IGlzIGtub3duIHRoZSBzZXF1ZW5jZSBpcyBhdCBsZWFzdCBhcyBsb25nIGFzIHRoZSBtZXNzYWdlLjxcL3A+XHJcblxyXG48cD5Zb3VyIHRhc2sgaXMgdG8gd3JpdGUgYSBwcm9ncmFtIHRoYXQgZXh0cmFjdHMgdGhlIG1lc3NhZ2UgdHJhbnNtaXR0ZWQgYnkgdGhlIHN0YXRpb24uIE1vcmUgZm9ybWFsbHksIHlvdXIgcHJvZ3JhbSBuZWVkcyB0byBcdWZiMDFuZCB0aGUgc2hvcnRlc3Qgc3Vic2VxdWVuY2UgUyZwcmltZTsgb2YgdGhlIGlucHV0IHNlcXVlbmNlIFMgc3VjaCB0aGF0IFMgaW4gdHVybiBpcyBhIHN1YnNlcXVlbmNlIG9mIHRoZSAoc3VmXHVmYjAxY2llbnRseSBsb25nKSByZXBldGl0aW9uIFMmcHJpbWU7ICsgUyZwcmltZTsgKyAmbWlkZG90OyZtaWRkb3Q7Jm1pZGRvdDsgKyBTJnByaW1lOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGlzIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIFx1ZmIwMXJzdCBsaW5lIGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgTCwgdGhlIGxlbmd0aCBvZiB0aGUgc2VxdWVuY2UgUy4gVGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIGV4YWN0bHkgTCBjaGFyYWN0ZXJzLCB0aGUgc2VxdWVuY2UgUyBpdHNlbGYuIFRoZSBzZXF1ZW5jZSBjb25zaXN0cyBvZiBsb3dlcmNhc2UgbGV0dGVycyAoYS4uLnopLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBwcm9ncmFtIHNob3VsZCB3cml0ZSBvbmUgbGluZSB0byBzdGFuZGFyZCBvdXRwdXQgY29udGFpbmluZyBhIHNpbmdsZSBpbnRlZ2VyOiB0aGUgbGVuZ3RoIEwmcHJpbWU7IG9mIHRoZSBtZXNzYWdlIFMmcHJpbWU7LiBOb3RlIHRoYXQgTCZwcmltZTsgbXVzdCBiZSB0aGUgc21hbGxlc3QgcG9zc2libGUuPFwvcD5cclxuIiwiaGludCI6IjxwPmhlIG1lc3NhZ2UgY291bGQgYmUgYWJjLCBjYWIgb3IgYWJjYWJjLCBidXQgdGhlcmUmcnNxdW87cyBubyBwb3NzaWJsZSBtZXNzYWdlIHNob3J0ZXIgdGhhbiAzIGNoYXJhY3RlcnMuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2009 P2번

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