시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 165 95 84 67.742%

문제

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

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

즉, 입력으로 S가 주어졌을 때, 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+XHVkNTVjIFx1Y2NhZFx1Y2RlOFx1Yzc5MFx1YWMwMCBcdWJjMWJcdWM3NDAgXHViYTU0XHVjMmRjXHVjOWMwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVkNTZkXHVjMGMxIFx1Y2NhZFx1Y2RlOFx1Yzc5MFx1YWMwMCBcdWJjMWJcdWM3NDAgXHViYTU0XHVjMmRjXHVjOWMwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCBcdWJjMjlcdWMxYTFcdWFkNmRcdWM1ZDBcdWMxMWMgXHViY2Y0XHViMGI4IFx1YmE1NFx1YzJkY1x1YzljMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWI3N2NcdWI1MTRcdWM2MjQgXHViYzI5XHVjMWExXHVhZDZkXHVjNWQwXHVjMTFjIFx1YmNmNFx1YjBiOCBcdWJhNTRcdWMyZGNcdWM5YzBcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlx1Yzk4OSwgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgU1x1YWMwMCBTJiMzOTsgKyBTJiMzOTsgKyAuLi4gKyBTJiMzOTtcdWM3NTggXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWI0MThcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YzllN1x1Yzc0MCBcdWJkODBcdWJkODRcdWMyMThcdWM1ZjQgUyYjMzk7XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBTXHVjNzU4IFx1YWUzOFx1Yzc3NCBMXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFlMzhcdWM3NzRcdWFjMDAgTFx1Yzc3OCBTXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViYTU0XHVjMmRjXHVjOWMwXHViMjk0IFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWMxOGNcdWJiMzhcdWM3OTBcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gKDEgJmxlOyBMICZsZTsmbmJzcDsxLDAwMCwwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBTJiMzOTtcdWM3NTggXHVhZTM4XHVjNzc0IEwmIzM5O1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YWMwMFx1YjJhNVx1ZDU1YyBcdWJhNTRcdWMyZGNcdWM5YzBcdWI4NWMgYWJjLCBjYWIsIGFiY2FiY1x1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YWUzOFx1Yzc3NFx1YWMwMCAzXHViY2Y0XHViMmU0IFx1YzllN1x1Yzc0MCBcdWJhNTRcdWMyZGNcdWM5YzBcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMzU2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUmFkaW8gVHJhbnNtaXNzaW9uIiwiZGVzY3JpcHRpb24iOiI8cD5BIHJhZGlvIHN0YXRpb24gbmVlZHMgdG8gdHJhbnNtaXQgYSBtZXNzYWdlIHRvIHNldmVyYWwgcmVjaXBpZW50cy4gVG8gZW5zdXJlIGFsbCBsaXN0ZW5lcnMgZ2V0IGl0LCB0aGUgbWVzc2FnZSBpcyBwbGF5ZWQgYWdhaW4gYW5kIGFnYWluIGluIGEgY29udGludW91cyBsb29wLjxcL3A+XHJcblxyXG48cD5Zb3UmcnNxdW87cmUgZ2l2ZW4gYSBzZXF1ZW5jZSBvZiBjaGFyYWN0ZXJzIHJlY2VpdmVkIGJ5IG9uZSBvZiB0aGUgcmVjaXBpZW50cy4gSXQgaXMga25vd24gdGhlIHNlcXVlbmNlIGlzIGF0IGxlYXN0IGFzIGxvbmcgYXMgdGhlIG1lc3NhZ2UuPFwvcD5cclxuXHJcbjxwPllvdXIgdGFzayBpcyB0byB3cml0ZSBhIHByb2dyYW0gdGhhdCBleHRyYWN0cyB0aGUgbWVzc2FnZSB0cmFuc21pdHRlZCBieSB0aGUgc3RhdGlvbi4gTW9yZSBmb3JtYWxseSwgeW91ciBwcm9ncmFtIG5lZWRzIHRvIFx1ZmIwMW5kIHRoZSBzaG9ydGVzdCBzdWJzZXF1ZW5jZSBTJnByaW1lOyBvZiB0aGUgaW5wdXQgc2VxdWVuY2UgUyBzdWNoIHRoYXQgUyBpbiB0dXJuIGlzIGEgc3Vic2VxdWVuY2Ugb2YgdGhlIChzdWZcdWZiMDFjaWVudGx5IGxvbmcpIHJlcGV0aXRpb24gUyZwcmltZTsgKyBTJnByaW1lOyArICZtaWRkb3Q7Jm1pZGRvdDsmbWlkZG90OyArIFMmcHJpbWU7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgaXMgcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0LiBUaGUgXHVmYjAxcnN0IGxpbmUgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciBMLCB0aGUgbGVuZ3RoIG9mIHRoZSBzZXF1ZW5jZSBTLiBUaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgZXhhY3RseSBMIGNoYXJhY3RlcnMsIHRoZSBzZXF1ZW5jZSBTIGl0c2VsZi4gVGhlIHNlcXVlbmNlIGNvbnNpc3RzIG9mIGxvd2VyY2FzZSBsZXR0ZXJzIChhLi4ueikuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIHByb2dyYW0gc2hvdWxkIHdyaXRlIG9uZSBsaW5lIHRvIHN0YW5kYXJkIG91dHB1dCBjb250YWluaW5nIGEgc2luZ2xlIGludGVnZXI6IHRoZSBsZW5ndGggTCZwcmltZTsgb2YgdGhlIG1lc3NhZ2UgUyZwcmltZTsuIE5vdGUgdGhhdCBMJnByaW1lOyBtdXN0IGJlIHRoZSBzbWFsbGVzdCBwb3NzaWJsZS48XC9wPlxyXG4iLCJoaW50IjoiPHA+aGUgbWVzc2FnZSBjb3VsZCBiZSBhYmMsIGNhYiBvciBhYmNhYmMsIGJ1dCB0aGVyZSZyc3F1bztzIG5vIHBvc3NpYmxlIG1lc3NhZ2Ugc2hvcnRlciB0aGFuIDMgY2hhcmFjdGVycy48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2009 P2번

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