시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB5409145878331.010%

문제

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

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

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

입력

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

출력

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

예제 입력 1

11
sabcabcfabc

예제 출력 1

3

예제 입력 2

18
trutrutiktiktappop

예제 출력 2

4

예제 입력 3

6
abcdef

예제 출력 3

0
W3sicHJvYmxlbV9pZCI6IjMwMzMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMDBcdWM3YTUgXHVhZTM0IFx1YmIzOFx1Yzc5MFx1YzVmNCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YWZjOFx1YzVkMFx1YzExYyBcdWFlMzhcdWM3NzRcdWFjMDAgTFx1Yzc3OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHVjNjc4XHVjNmUwXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFmYzhcdWM1ZDBcdWMxMWMgXHVhZTZjIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3NzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1Yzg4NVx1Yzc3NFx1YzVkMCBcdWM4MDFcdWM1YzhcdWIyZTQuIFx1Yzg4NVx1Yzc3NFx1Yjk3YyBcdWM4MDFcdWIzNTggXHVjOTExXHVjNWQwIFx1YzViNFx1YjVhNCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAgXHViNDUwIFx1YmM4OCBcdWM3NzRcdWMwYzEgXHViNGYxXHVjN2E1XHVkNTU4XHViMjk0IFx1YWM4MyBcdWFjMTlcdWM3NDAgXHViMjkwXHViMDhjXHVjNzQ0IFx1YmMxYlx1YzU1OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YjQ1MCBcdWJjODggXHVjNzc0XHVjMGMxIFx1YjRmMVx1YzdhNVx1ZDU1YyBcdWJkODBcdWJkODQgXHViYjM4XHVjNzkwXHVjNWY0IFx1YzkxMSBcdWFjMDBcdWM3YTUgXHVhZTM4XHVjNzc0XHVhYzAwIFx1YWUzNCBcdWFjODNcdWM3NDQgXHVjYzNlXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIChcdWJkODBcdWJkODRcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAgXHVhY2I5XHVjY2QwXHVjMTFjIFx1YjRmMVx1YzdhNVx1ZDU2MCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0KTxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBMXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBMICZsZTsgMjAwLDAwMCkgXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFlMzhcdWM3NzRcdWFjMDAgTFx1Yzc3NFx1YmE3NFx1YzExYyBcdWM1NGNcdWQzMGNcdWJjYjMgXHVjMThjXHViYjM4XHVjNzkwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViNDUwIFx1YmM4OCBcdWM3NzRcdWMwYzEgXHViNGYxXHVjN2E1XHVkNTU4XHViMjk0IFx1YmQ4MFx1YmQ4NCBcdWJiMzhcdWM3OTBcdWM1ZjQgXHVjOTExIFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWFjMDBcdWM3YTUgXHVhZTM0IFx1YWM4M1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QgXHVhZGY4XHViN2VjXHVkNTVjIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM1YzZcdWM3NDQgXHViNTRjXHViMjk0IDBcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjMwMzMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJEVkFQVVQiLCJkZXNjcmlwdGlvbiI6IjxwPkl2YW5hIHdvbiB0aGUgYmV0IChadm9ua28gaGFkbiYjMzk7dCBmb3Jlc2VlbiB0aGlzIGFuZCBzdXNwZWN0cyB0aGF0IGl0IGlzIGR1ZSB0byBvdXRzaWRlIGludGVyZmVyZW5jZSkgYW5kIG5vdyBadm9ua28gaXMgd2FpdGluZyBmb3IgaGVyIGF0IHRoZSBtb3ZpZXMuIFdoaWxlIGhlIGlzIHdhaXRpbmcsIGhlIGlzIG9ic2VydmluZyBtZXNzYWdlcyBvbiBhIHNjcmVlbiBhYm92ZSBoaW0uJm5ic3A7PFwvcD5cclxuXHJcbjxwPkFzIEl2YW5hIGlzIHJ1bm5pbmcgbGF0ZSwgWnZvbmtvIGhhcyBiZWVuIGxvb2tpbmcgYXQgdGhlIHNjcmVlbiBmb3IgYSB3aGlsZSBhbmQgbm90aWNlZCB0aGF0IHNvbWUgbWVzc2FnZXMgYXBwZWFyZWQgb24gdGhlIHNjcmVlbiBtb3JlIHRoYW4gb25jZS4gTmF0dXJhbGx5LCBoZSYjMzk7cyBiZWVuIHdyaXRpbmcgZG93biBhbGwgbWVzc2FnZXMgb24gYSBwaWVjZSBvZiBwYXBlci4gSGUgd2FudHMgdG8ga25vdyB0aGUgbGVuZ3RoIG9mIHRoZSBsb25nZXN0IHN0cmluZyB0aGF0IGFwcGVhcmVkIGF0IGxlYXN0IHR3aWNlIChhcHBlYXJzIGluIHR3byBkaWZmZXJlbnQgcG9zaXRpb25zIG9uIHRoZSBwYXBlcikuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhbiBpbnRlZ2VyIEwgKDEgJmxlOyBMICZsZTsgMjAwIDAwMCksIHRoZSBsZW5ndGggb2YgdGhlIHN0cmluZyBadm9ua28gd3JvdGUgZG93bi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIGEgc3RyaW5nIG9mIEwgbG93ZXJjYXNlIGxldHRlciBvZiB0aGUgRW5nbGlzaCBhbHBoYWJldC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIGxlbmd0aCBvZiB0aGUgbG9uZ2VzdCBzdHJpbmcgdGhhdCBhcHBlYXJzIHR3aWNlIG9uIGEgc2luZ2xlIGxpbmUuIElmIHRoZXJlIGlzIG5vIHN1Y2ggc3RyaW5nLCBvdXRwdXQgemVyby4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

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