시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 2591 749 544 33.252%

문제

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

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

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

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

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

입력

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

출력

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

예제 입력 1

abcdabcabb

예제 출력 1

3
W3sicHJvYmxlbV9pZCI6IjE3MDEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJDdWJlZGl0b3IiLCJkZXNjcmlwdGlvbiI6IjxwPkN1YmVsb3Zlclx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3OThcdWJjMGQgXHVjNWI4XHVjNWI0IFdoaXRlc3BhY2VcdWM3NTggXHVjZjU0XHViNTI5XHVjNzQ0IFx1YjNjNFx1YzY0MFx1YzhmY1x1YjI5NCBcdWM1YjhcdWM1YjRcdWM3NzggQ3ViZWxhbmdcdWM3NDQgXHViOWNjXHViNGU0XHVjNWM4XHViMmU0LiBDdWJlbGFuZ1x1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NzQgXHVjZjU0XHViNTI5XHVjNzQ0IFx1ZDU1OFx1YjJlNFx1YmNmNFx1YjJjOCwgXHVjODEwXHVjODEwIFx1Yzc3NCBcdWM1YjhcdWM1YjRcdWM1ZDAgXHViOWRlXHViMjk0IFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWM1ZDBcdWI1MTRcdWQxMzBcdWFjMDAgXHVkNTQ0XHVjNjk0XHVkNTU4XHVhYzhjIFx1YjQxOFx1YzVjOFx1YjJlNC4gXHVjNjI0XHViNzljIFx1YzJkY1x1YWMwNCBcdWFjZTBcdWMwZGRcdWQ1NWMgXHViMDVkXHVjNWQwIFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWM1ZDBcdWI1MTRcdWQxMzBcdWI5N2MgXHViOWNjXHViNGU0XHVhYzhjIFx1YjQxOFx1YzVjOFx1YWNlMCwgXHVhZGY4IFx1YzVkMFx1YjUxNFx1ZDEzMFx1Yzc1OCBcdWM3NzRcdWI5ODRcdWM3NDAgQ3ViZWRpdG9yXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQxNGRcdWMyYTRcdWQyYjggXHVjNWQwXHViNTE0XHVkMTMwXHViMjk0IFx1Y2MzZVx1YWUzMCBcdWFlMzBcdWIyYTVcdWM3NDQgXHVjOWMwXHVjNmQwXHVkNTVjXHViMmU0LiBcdWIzMDBcdWJkODBcdWJkODRcdWM3NTggXHVjNWQwXHViNTE0XHVkMTMwXHViMjk0IFx1Y2MzZVx1YzczY1x1YjgyNFx1YWNlMCBcdWQ1NThcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YjJlOCBcdWQ1NWMgXHViYzg4XHViOWNjIFx1YjA5OFx1YzY0MFx1YjNjNCBcdWNjM2VcdWIyOTRcdWIyZTQuIEN1YmVsb3Zlclx1YjI5NCBcdWM3NzQgXHVhZTMwXHViMmE1XHVjNzQwIEN1YmVsYW5nXHVjNWQwIFx1YmQ4MFx1YzgwMVx1ZDU2OVx1ZDU1OFx1YjJlNFx1YWNlMCBcdWMwZGRcdWFjMDFcdWQ1ODhcdWIyZTQuIEN1YmVsYW5nXHVjNWQwXHVjMTFjIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWFlMzBcdWIyYTVcdWM3NDAgXHVjNWI0XHViNWE0IFx1YmIzOFx1Yzc5MFx1YzVmNCBcdWIwYjRcdWM1ZDBcdWMxMWMgXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWI0NTAgXHViYzg4IFx1Yzc3NFx1YzBjMSBcdWIwOThcdWM2MjRcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1Y2MzZVx1YjI5NCBcdWFlMzBcdWIyYTVcdWM3NzRcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHViNDUwIFx1YmQ4MFx1YmQ4NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAgXHVhY2I5XHVjY2QwXHViM2M0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgYWJjZGFiY1x1YzVkMFx1YzExYyBhYmNcdWIyOTQgXHViNDUwIFx1YmM4OCBcdWIwOThcdWM2MjRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YWM4MFx1YzBjOVx1Yzc3NCBcdWFjMDBcdWIyYTVcdWQ1NThcdWM5YzBcdWI5Y2MsIGFiY2RcdWIyOTQgXHVkNTVjIFx1YmM4OCBcdWIwOThcdWM2MjRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YWM4MFx1YzBjOVx1Yzc3NCBcdWI0MThcdWM5YzBcdWI5N2MgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWI4MDdcdWFjOGMgXHVjNWI0XHViNWE0Jm5ic3A7XHViYjM4XHVjNzkwXHVjNWY0XHVjNWQwXHVjMTFjIFx1YjQ1MCBcdWJjODggXHVjNzc0XHVjMGMxIFx1YjA5OFx1YzYyNFx1YjI5NCBcdWJkODBcdWJkODQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwIFx1YjllNFx1YzZiMCBcdWI5Y2VcdWM3NDQgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViN2VjXHVkNTVjIFx1YmQ4MFx1YmQ4NCBcdWJiMzhcdWM3OTBcdWM1ZjQgXHVjOTExXHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWFlMzhcdWM3NzRcdWFjMDAgXHVhZTM0IFx1YWM4M1x1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgYWJjYWJjYWJjXHVjNWQwXHVjMTFjIGFiY1x1YjI5NCBcdWMxMzgmbmJzcDtcdWJjODggXHViMDk4XHVjNjI0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCZuYnNwO1x1YWM4MFx1YzBjOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWI2MTAsIGFiY2FiY1x1YjNjNCBcdWI0NTAmbmJzcDtcdWJjODggXHViMDk4XHVjNjI0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWFjODBcdWMwYzlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBhYmNhYmNhXHViMjk0IFx1ZDU1YyZuYnNwO1x1YmM4OCBcdWIwOThcdWM2MjRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YWM4MFx1YzBjOVx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YjQ1MCZuYnNwO1x1YmM4OCBcdWM3NzRcdWMwYzEgXHViMDk4XHVjNjI0XHViMjk0IFx1YmQ4MFx1YmQ4NCBcdWJiMzhcdWM3OTBcdWM1ZjQgXHVjOTExXHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWFlMzQgXHVhYzgzXHVjNzQwIGFiY2FiY1x1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1Yzc3NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHViMmY1XHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCBcdWNkNWNcdWIzMDAgNSwwMDBcdWM3NzRcdWFjZTAsIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0MCBcdWJhYThcdWI0NTAgXHVjMThjXHViYjM4XHVjNzkwXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNWQwXHVjMTFjIFx1YzhmY1x1YzViNFx1YzljNCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHViNDUwIFx1YmM4OFx1Yzc3NFx1YzBjMSBcdWIwOThcdWM2MjRcdWIyOTQgXHViZDgwXHViZDg0XHViYjM4XHVjNzkwXHVjNWY0IFx1YzkxMVx1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHVhZTM0IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTcwMSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkVkaXRvciIsImRlc2NyaXB0aW9uIjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9lZGl0b3IoMSkucG5nXCIgc3R5bGU9XCJmbG9hdDpyaWdodDsgaGVpZ2h0OjE5NXB4OyB3aWR0aDozMDRweFwiIFwvPk1yLiBLaW0gaXMgYSBwcm9mZXNzaW9uYWwgcHJvZ3JhbW1lci4gUmVjZW50bHkgaGUgd2FudHMgdG8gZGVzaWduIGEgbmV3IGVkaXRvciB3aGljaCBoYXMgYXMgbWFueSBmdW5jdGlvbnMgYXMgcG9zc2libGUuIE1vc3QgZWRpdG9ycyBzdXBwb3J0IGEgc2ltcGxlIHNlYXJjaCBmdW5jdGlvbiB0aGF0IGZpbmRzIG9uZSBvY2N1cnJlbmNlIChvciBhbGwgb2NjdXJyZW5jZXMgc3VjY2Vzc2l2ZWx5KSBvZiBhIHF1ZXJ5IHBhdHRlcm4gc3RyaW5nIGluIHRoZSB0ZXh0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5IZSBvYnNlcnZlZCB0aGF0IHRoZSBzZWFyY2ggZnVuY3Rpb24gaW4gY29tbWVyY2lhbCBlZGl0b3JzIGRvZXMgbm90aGluZyBpZiBubyBxdWVyeSBwYXR0ZXJuIGlzIGdpdmVuLiBIaXMgaWRlYSBvZiBhIG5ldyBzZWFyY2ggZnVuY3Rpb24gcmVnYXJkcyBlYWNoIHN1YnN0cmluZyBvZiB0aGUgZ2l2ZW4gdGV4dCBhcyBhIHF1ZXJ5IHBhdHRlcm4gc3RyaW5nIGl0c2VsZiBhbmQgaGlzIG5ldyBmdW5jdGlvbiBmaW5kcyBhbm90aGVyIG9jY3VycmVuY2UgaW4gdGhlIHRleHQuIFRoZSBwcm9ibGVtIGlzIHRoYXQgdGhlcmUgY2FuIGJlIG9jY3VycmVuY2VzIG9mIG1hbnkgc3Vic3RyaW5ncyBpbiB0aGUgdGV4dC4gU28sIE1yLiBLaW0gZGVjaWRlcyB0aGF0IHRoZSBuZXcgZnVuY3Rpb24gZmluZHMgb25seSBvY2N1cnJlbmNlcyBvZiB0aGUgbG9uZ2VzdCBzdWJzdHJpbmcgaW4gdGhlIHRleHQgaW4gb3JkZXIgdG8gcmVtZWR5IHRoZSBwcm9ibGVtLiBBIGZvcm1hbCBkZWZpbml0aW9uIG9mIHRoZSBzZWFyY2ggZnVuY3Rpb24gaXMgYXMgZm9sbG93czombmJzcDs8XC9wPlxyXG5cclxuPHA+R2l2ZW4gYSB0ZXh0IHN0cmluZyBTLCBmaW5kIHRoZSBsb25nZXN0IHN1YnN0cmluZyBpbiB0ZXh0IHN0cmluZyBTIHN1Y2ggdGhhdCB0aGUgc3Vic3RyaW5nIGFwcGVhcnMgYXQgbGVhc3QgdHdpY2UuIFRoZSB0d28gb2NjdXJyZW5jZXMgYXJlIGFsbG93ZWQgdG8gb3ZlcmxhcC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byByZWFkIGZyb20gc3RhbmRhcmQgaW5wdXQuIFRoZSBpbnB1dCBjb25zaXN0cyBvZiBUIHRlc3QgY2FzZXMuIFRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyBUIGlzIGdpdmVuIGluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dC4gRm9yIGVhY2ggdGVzdCBjYXNlLCBhIHRleHQgc3RyaW5nIFMgaXMgZ2l2ZW4gaW4gb25lIGxpbmUuIEZvciBldmVyeSBzdHJpbmcsIHRoZSBsZW5ndGggaXMgbGVzcyB0aGFuIG9yIGVxdWFsIHRvIDUsMDAwIGFuZCB0aGUgYWxwaGFiZXQgJnN1bTsgaXMgdGhlIHNldCBvZiBsb3dlcmNhc2UgRW5nbGlzaCBjaGFyYWN0ZXJzLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFByaW50IGV4YWN0bHkgb25lIGxpbmUgZm9yIGVhY2ggdGVzdCBjYXNlLiBQcmludCB0aGUgbGVuZ3RoIG9mIHRoZSBsb25nZXN0IHN1YnN0cmluZyBpbiB0ZXh0IHN0cmluZyBTIHN1Y2ggdGhhdCB0aGUgc3Vic3RyaW5nIGFwcGVhcnMgYXQgbGVhc3QgdHdpY2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgc2hvd3Mgc2FtcGxlIGlucHV0IGFuZCBvdXRwdXQgZm9yIHRocmVlIHRlc3QgY2FzZXMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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