시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 1991 601 433 33.104%

문제

Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 몇 일 동안 고생한 끝에 새로운 에디터를 만들게 되었고, 그 에디터의 이름은 Cubeditor이다.

텍스트 에디터는 찾기 기능을 지원한다. 대부분의 에디터는 찾으려고 하는 문자열이 단 한 번만 나와도 찾는다. Cubelover는 이 기능은 Cubelang에 부적합하다고 생각했다. Cubelang에서 필요한 기능은 어떤 문자열 내에서 부분 문자열이 두 번 이상 나오는 문자열을 찾는 기능이다. 이 때, 두 부분 문자열은 겹쳐도 된다.

예를 들어, abcdabc에서 abc는 두 번 나오기 때문에 검색이 가능하지만, abcd는 한 번 나오기 때문에 검색이 되지를 않는다.

이렇게 어떤 문자열에서 두 번 이상 나오는 부분 문자열은 매우 많을 수도 있다. 이러한 부분 문자열 중에서 가장 길이가 긴 것을 구하는 프로그램을 작성하시오.

예를 들어, abcabcabc에서 abc는 세 번 나오기 때문에 검색할 수 있다. 또, abcabc도 두 번 나오기 때문에 검색할 수 있다. 하지만, abcabca는 한 번 나오기 때문에 검색할 수 없다. 따라서, 두 번 이상 나오는 부분 문자열 중에서 가장 긴 것은 abcabc이기 때문에, 이 문자열이 답이 된다.

입력

첫째 줄에 문자열이 주어진다. 문자열의 길이는 최대 5,000이고, 문자열은 모두 소문자로만 이루어져 있다.

출력

입력에서 주어진 문자열의 두 번이상 나오는 부분문자열 중에서 가장 긴 길이를 출력한다.

예제 입력 1

abcdabcabb

예제 출력 1

3
W3sicHJvYmxlbV9pZCI6IjE3MDEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJDdWJlZGl0b3IiLCJkZXNjcmlwdGlvbiI6IjxwPkN1YmVsb3Zlclx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3OThcdWJjMGQgXHVjNWI4XHVjNWI0IFdoaXRlc3BhY2VcdWM3NTggXHVjZjU0XHViNTI5XHVjNzQ0IFx1YjNjNFx1YzY0MFx1YzhmY1x1YjI5NCBcdWM1YjhcdWM1YjRcdWM3NzggQ3ViZWxhbmdcdWM3NDQgXHViOWNjXHViNGU0XHVjNWM4XHViMmU0LiBDdWJlbGFuZ1x1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NzQgXHVjZjU0XHViNTI5XHVjNzQ0IFx1ZDU1OFx1YjJlNFx1YmNmNFx1YjJjOCwgXHVjODEwXHVjODEwIFx1Yzc3NCBcdWM1YjhcdWM1YjRcdWM1ZDAgXHViOWRlXHViMjk0IFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWM1ZDBcdWI1MTRcdWQxMzBcdWFjMDAgXHVkNTQ0XHVjNjk0XHVkNTU4XHVhYzhjIFx1YjQxOFx1YzVjOFx1YjJlNC4gXHViYTg3IFx1Yzc3YyBcdWIzZDlcdWM1NDggXHVhY2UwXHVjMGRkXHVkNTVjIFx1YjA1ZFx1YzVkMCBcdWMwYzhcdWI4NWNcdWM2YjQgXHVjNWQwXHViNTE0XHVkMTMwXHViOTdjIFx1YjljY1x1YjRlNFx1YWM4YyBcdWI0MThcdWM1YzhcdWFjZTAsIFx1YWRmOCBcdWM1ZDBcdWI1MTRcdWQxMzBcdWM3NTggXHVjNzc0XHViOTg0XHVjNzQwIEN1YmVkaXRvclx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMTRkXHVjMmE0XHVkMmI4IFx1YzVkMFx1YjUxNFx1ZDEzMFx1YjI5NCBcdWNjM2VcdWFlMzAgXHVhZTMwXHViMmE1XHVjNzQ0IFx1YzljMFx1YzZkMFx1ZDU1Y1x1YjJlNC4gXHViMzAwXHViZDgwXHViZDg0XHVjNzU4IFx1YzVkMFx1YjUxNFx1ZDEzMFx1YjI5NCBcdWNjM2VcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTU4XHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWIyZTggXHVkNTVjIFx1YmM4OFx1YjljYyBcdWIwOThcdWM2NDBcdWIzYzQgXHVjYzNlXHViMjk0XHViMmU0LiBDdWJlbG92ZXJcdWIyOTQgXHVjNzc0IFx1YWUzMFx1YjJhNVx1Yzc0MCBDdWJlbGFuZ1x1YzVkMCBcdWJkODBcdWM4MDFcdWQ1NjlcdWQ1NThcdWIyZTRcdWFjZTAgXHVjMGRkXHVhYzAxXHVkNTg4XHViMmU0LiBDdWJlbGFuZ1x1YzVkMFx1YzExYyBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVhZTMwXHViMmE1XHVjNzQwIFx1YzViNFx1YjVhNCBcdWJiMzhcdWM3OTBcdWM1ZjQgXHViMGI0XHVjNWQwXHVjMTFjIFx1YmQ4MFx1YmQ4NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHViNDUwIFx1YmM4OCBcdWM3NzRcdWMwYzEgXHViMDk4XHVjNjI0XHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWNjM2VcdWIyOTQgXHVhZTMwXHViMmE1XHVjNzc0XHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWI0NTAgXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0MCBcdWFjYjlcdWNjZDBcdWIzYzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBhYmNkYWJjXHVjNWQwXHVjMTFjIGFiY1x1YjI5NCBcdWI0NTAgXHViYzg4IFx1YjA5OFx1YzYyNFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVhYzgwXHVjMGM5XHVjNzc0IFx1YWMwMFx1YjJhNVx1ZDU1OFx1YzljMFx1YjljYywgYWJjZFx1YjI5NCBcdWQ1NWMgXHViYzg4IFx1YjA5OFx1YzYyNFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVhYzgwXHVjMGM5XHVjNzc0IFx1YjQxOFx1YzljMFx1Yjk3YyBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YjgwN1x1YWM4YyBcdWM1YjRcdWI1YTQmbmJzcDtcdWJiMzhcdWM3OTBcdWM1ZjRcdWM1ZDBcdWMxMWMgXHViNDUwIFx1YmM4OCBcdWM3NzRcdWMwYzEgXHViMDk4XHVjNjI0XHViMjk0IFx1YmQ4MFx1YmQ4NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAgXHViOWU0XHVjNmIwIFx1YjljZVx1Yzc0NCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNCBcdWM5MTFcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWFlMzQgXHVhYzgzXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBhYmNhYmNhYmNcdWM1ZDBcdWMxMWMgYWJjXHViMjk0IFx1YzEzOCZuYnNwO1x1YmM4OCBcdWIwOThcdWM2MjRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwJm5ic3A7XHVhYzgwXHVjMGM5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjYxMCwgYWJjYWJjXHViM2M0IFx1YjQ1MCZuYnNwO1x1YmM4OCBcdWIwOThcdWM2MjRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YWM4MFx1YzBjOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIGFiY2FiY2FcdWIyOTQgXHVkNTVjJm5ic3A7XHViYzg4IFx1YjA5OFx1YzYyNFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVhYzgwXHVjMGM5XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHViNDUwJm5ic3A7XHViYzg4IFx1Yzc3NFx1YzBjMSBcdWIwOThcdWM2MjRcdWIyOTQgXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNCBcdWM5MTFcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1YWUzNCBcdWFjODNcdWM3NDAgYWJjYWJjXHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjNzc0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWIyZjVcdWM3NzQgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IFx1Y2Q1Y1x1YjMwMCA1LDAwMFx1Yzc3NFx1YWNlMCwgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWMxOGNcdWJiMzhcdWM3OTBcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM1ZDBcdWMxMWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWI0NTAgXHViYzg4XHVjNzc0XHVjMGMxIFx1YjA5OFx1YzYyNFx1YjI5NCBcdWJkODBcdWJkODRcdWJiMzhcdWM3OTBcdWM1ZjQgXHVjOTExXHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWFlMzQgXHVhZTM4XHVjNzc0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxNzAxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRWRpdG9yIiwiZGVzY3JpcHRpb24iOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2VkaXRvcigxKS5wbmdcIiBzdHlsZT1cImZsb2F0OnJpZ2h0OyBoZWlnaHQ6MTk1cHg7IHdpZHRoOjMwNHB4XCIgXC8+TXIuIEtpbSBpcyBhIHByb2Zlc3Npb25hbCBwcm9ncmFtbWVyLiBSZWNlbnRseSBoZSB3YW50cyB0byBkZXNpZ24gYSBuZXcgZWRpdG9yIHdoaWNoIGhhcyBhcyBtYW55IGZ1bmN0aW9ucyBhcyBwb3NzaWJsZS4gTW9zdCBlZGl0b3JzIHN1cHBvcnQgYSBzaW1wbGUgc2VhcmNoIGZ1bmN0aW9uIHRoYXQgZmluZHMgb25lIG9jY3VycmVuY2UgKG9yIGFsbCBvY2N1cnJlbmNlcyBzdWNjZXNzaXZlbHkpIG9mIGEgcXVlcnkgcGF0dGVybiBzdHJpbmcgaW4gdGhlIHRleHQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkhlIG9ic2VydmVkIHRoYXQgdGhlIHNlYXJjaCBmdW5jdGlvbiBpbiBjb21tZXJjaWFsIGVkaXRvcnMgZG9lcyBub3RoaW5nIGlmIG5vIHF1ZXJ5IHBhdHRlcm4gaXMgZ2l2ZW4uIEhpcyBpZGVhIG9mIGEgbmV3IHNlYXJjaCBmdW5jdGlvbiByZWdhcmRzIGVhY2ggc3Vic3RyaW5nIG9mIHRoZSBnaXZlbiB0ZXh0IGFzIGEgcXVlcnkgcGF0dGVybiBzdHJpbmcgaXRzZWxmIGFuZCBoaXMgbmV3IGZ1bmN0aW9uIGZpbmRzIGFub3RoZXIgb2NjdXJyZW5jZSBpbiB0aGUgdGV4dC4gVGhlIHByb2JsZW0gaXMgdGhhdCB0aGVyZSBjYW4gYmUgb2NjdXJyZW5jZXMgb2YgbWFueSBzdWJzdHJpbmdzIGluIHRoZSB0ZXh0LiBTbywgTXIuIEtpbSBkZWNpZGVzIHRoYXQgdGhlIG5ldyBmdW5jdGlvbiBmaW5kcyBvbmx5IG9jY3VycmVuY2VzIG9mIHRoZSBsb25nZXN0IHN1YnN0cmluZyBpbiB0aGUgdGV4dCBpbiBvcmRlciB0byByZW1lZHkgdGhlIHByb2JsZW0uIEEgZm9ybWFsIGRlZmluaXRpb24gb2YgdGhlIHNlYXJjaCBmdW5jdGlvbiBpcyBhcyBmb2xsb3dzOiZuYnNwOzxcL3A+XHJcblxyXG48cD5HaXZlbiBhIHRleHQgc3RyaW5nIFMsIGZpbmQgdGhlIGxvbmdlc3Qgc3Vic3RyaW5nIGluIHRleHQgc3RyaW5nIFMgc3VjaCB0aGF0IHRoZSBzdWJzdHJpbmcgYXBwZWFycyBhdCBsZWFzdCB0d2ljZS4gVGhlIHR3byBvY2N1cnJlbmNlcyBhcmUgYWxsb3dlZCB0byBvdmVybGFwLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGlucHV0IGNvbnNpc3RzIG9mIFQgdGVzdCBjYXNlcy4gVGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIFQgaXMgZ2l2ZW4gaW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0LiBGb3IgZWFjaCB0ZXN0IGNhc2UsIGEgdGV4dCBzdHJpbmcgUyBpcyBnaXZlbiBpbiBvbmUgbGluZS4gRm9yIGV2ZXJ5IHN0cmluZywgdGhlIGxlbmd0aCBpcyBsZXNzIHRoYW4gb3IgZXF1YWwgdG8gNSwwMDAgYW5kIHRoZSBhbHBoYWJldCAmc3VtOyBpcyB0aGUgc2V0IG9mIGxvd2VyY2FzZSBFbmdsaXNoIGNoYXJhY3RlcnMuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHdyaXRlIHRvIHN0YW5kYXJkIG91dHB1dC4gUHJpbnQgZXhhY3RseSBvbmUgbGluZSBmb3IgZWFjaCB0ZXN0IGNhc2UuIFByaW50IHRoZSBsZW5ndGggb2YgdGhlIGxvbmdlc3Qgc3Vic3RyaW5nIGluIHRleHQgc3RyaW5nIFMgc3VjaCB0aGF0IHRoZSBzdWJzdHJpbmcgYXBwZWFycyBhdCBsZWFzdCB0d2ljZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBzaG93cyBzYW1wbGUgaW5wdXQgYW5kIG91dHB1dCBmb3IgdGhyZWUgdGVzdCBjYXNlcy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Seoul 2007 B번

  • 잘못된 데이터를 찾은 사람: atomzeno
  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: klimmek55