시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1462 363 194 27.596%

문제

상근이는 꿈에서 길이가 L인 문자열을 외웠다.

꿈에서 깬 상근이는 이 문자열을 종이에 적었다. 종이를 적던 중에 어떤 문자열은 두 번 이상 등장하는 것 같은 느낌을 받았다.

문자열이 주어졌을 때, 두 번 이상 등장한 부분 문자열 중 가장 길이가 긴 것을 찾는 프로그램을 작성하시오. (부분문자열은 겹쳐서 등장할 수도 있다)

입력

첫째 줄에 L이 주어진다. (1 ≤ L ≤ 200,000) 다음 줄에는 길이가 L이면서 알파벳 소문자로 이루어진 문자열이 주어진다.

출력

첫째 줄에 두 번 이상 등장하는 부분 문자열 중 길이가 가장 긴 것의 길이를 출력한다. 만약 그러한 문자열이 없을 때는 0을 출력한다.

예제 입력 1

11
sabcabcfabc

예제 출력 1

3
W3sicHJvYmxlbV9pZCI6IjMwMzMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMDBcdWM3YTUgXHVhZTM0IFx1YmIzOFx1Yzc5MFx1YzVmNCIsImRlc2NyaXB0aW9uIjoiXHJcbjxwPlxyXG5cdFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWFmYzhcdWM1ZDBcdWMxMWMgXHVhZTM4XHVjNzc0XHVhYzAwIExcdWM3NzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1YzY3OFx1YzZlMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVhZmM4XHVjNWQwXHVjMTFjIFx1YWU2YyBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNzc0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWM4ODVcdWM3NzRcdWM1ZDAgXHVjODAxXHVjNWM4XHViMmU0LiBcdWM4ODVcdWM3NzRcdWI5N2MgXHVjODAxXHViMzU4IFx1YzkxMVx1YzVkMCBcdWM1YjRcdWI1YTQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwIFx1YjQ1MCBcdWJjODggXHVjNzc0XHVjMGMxIFx1YjRmMVx1YzdhNVx1ZDU1OFx1YjI5NCBcdWFjODMgXHVhYzE5XHVjNzQwIFx1YjI5MFx1YjA4Y1x1Yzc0NCBcdWJjMWJcdWM1NThcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWI0NTAgXHViYzg4IFx1Yzc3NFx1YzBjMSBcdWI0ZjFcdWM3YTVcdWQ1NWMgXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNCBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWFlMzQgXHVhYzgzXHVjNzQ0IFx1Y2MzZVx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiAoXHViZDgwXHViZDg0XHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwIFx1YWNiOVx1Y2NkMFx1YzExYyBcdWI0ZjFcdWM3YTVcdWQ1NjAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNCk8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTCAmbGU7IDIwMCwwMDApIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZTM4XHVjNzc0XHVhYzAwIExcdWM3NzRcdWJhNzRcdWMxMWMgXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjQ1MCBcdWJjODggXHVjNzc0XHVjMGMxIFx1YjRmMVx1YzdhNVx1ZDU1OFx1YjI5NCBcdWJkODBcdWJkODQgXHViYjM4XHVjNzkwXHVjNWY0IFx1YzkxMSBcdWFlMzhcdWM3NzRcdWFjMDAgXHVhYzAwXHVjN2E1IFx1YWUzNCBcdWFjODNcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkIFx1YWRmOFx1YjdlY1x1ZDU1YyBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjNWM2XHVjNzQ0IFx1YjU0Y1x1YjI5NCAwXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMDMzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRFZBUFVUIiwiZGVzY3JpcHRpb24iOiI8cD5JdmFuYSB3b24gdGhlIGJldCAoWnZvbmtvIGhhZG4mIzM5O3QgZm9yZXNlZW4gdGhpcyBhbmQgc3VzcGVjdHMgdGhhdCBpdCBpcyBkdWUgdG8gb3V0c2lkZSBpbnRlcmZlcmVuY2UpIGFuZCBub3cgWnZvbmtvIGlzIHdhaXRpbmcgZm9yIGhlciBhdCB0aGUgbW92aWVzLiBXaGlsZSBoZSBpcyB3YWl0aW5nLCBoZSBpcyBvYnNlcnZpbmcgbWVzc2FnZXMgb24gYSBzY3JlZW4gYWJvdmUgaGltLiZuYnNwOzxcL3A+XHJcblxyXG48cD5BcyBJdmFuYSBpcyBydW5uaW5nIGxhdGUsIFp2b25rbyBoYXMgYmVlbiBsb29raW5nIGF0IHRoZSBzY3JlZW4gZm9yIGEgd2hpbGUgYW5kIG5vdGljZWQgdGhhdCBzb21lIG1lc3NhZ2VzIGFwcGVhcmVkIG9uIHRoZSBzY3JlZW4gbW9yZSB0aGFuIG9uY2UuIE5hdHVyYWxseSwgaGUmIzM5O3MgYmVlbiB3cml0aW5nIGRvd24gYWxsIG1lc3NhZ2VzIG9uIGEgcGllY2Ugb2YgcGFwZXIuIEhlIHdhbnRzIHRvIGtub3cgdGhlIGxlbmd0aCBvZiB0aGUgbG9uZ2VzdCBzdHJpbmcgdGhhdCBhcHBlYXJlZCBhdCBsZWFzdCB0d2ljZSAoYXBwZWFycyBpbiB0d28gZGlmZmVyZW50IHBvc2l0aW9ucyBvbiB0aGUgcGFwZXIpLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYW4gaW50ZWdlciBMICgxICZsZTsgTCAmbGU7IDIwMCAwMDApLCB0aGUgbGVuZ3RoIG9mIHRoZSBzdHJpbmcgWnZvbmtvIHdyb3RlIGRvd24uJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBjb250YWlucyBhIHN0cmluZyBvZiBMIGxvd2VyY2FzZSBsZXR0ZXIgb2YgdGhlIEVuZ2xpc2ggYWxwaGFiZXQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBsZW5ndGggb2YgdGhlIGxvbmdlc3Qgc3RyaW5nIHRoYXQgYXBwZWFycyB0d2ljZSBvbiBhIHNpbmdsZSBsaW5lLiBJZiB0aGVyZSBpcyBubyBzdWNoIHN0cmluZywgb3V0cHV0IHplcm8uJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2006/2007 > Contest #5 6번