시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 108 27 16 24.242%

문제

윤표는 만사가 귀찮은 친구다. 그래서 문자열을 입력할 때, 중복되는 부분이 있으면, 앞서 나온 부분 문자열을 복사해서 붙여넣어야 마음이 편안하다.

윤표는 매번 자신이 위치를 직접 기억하여 붙여넣다가, 복사붙여넣기를 도와주는 프로그램을 만들려고 한다.

문자열이 주어졌을 때, 해당 문자열에서 겹치지 않게 두 번 이상 반복되는 가장 긴 부분 문자열과 해당 문자열의 길이를 출력하는 프로그램을 작성하시오.

입력

알파벳 소문자로 이루어진 문자열이 주어진다. 주어지는 문자열의 길이는 1 이상 200,000 이하이다. 

출력

주어진 문자열에서 겹치지 않게 (disjoint) 두 번 이상 등장하는 가장 긴 문자열의 길이를 공백을 기준으로 출력한다.

단, 조건을 만족하는 문자열이 없는 경우 -1을 출력한다.

예제 입력 1

applebananacarrotapple

예제 출력 1

5

apple이 1~5번째, 18~22번째 글자에서 두 번 나타납니다.

예제 입력 2

abcdefghijklmnop

예제 출력 2

-1

반복되는 문자열이 없습니다.

예제 입력 3

dotzsdultvofkudispdoowrhwldssvtzldwiyihpjwsxfdvjhbdubeiojlcnzjazvtzldwiyihpjwsxfdvjhbdubvxgrwe

예제 출력 3

24

vtzldwiyihpjwsxfdvjhbdub가 30~53번째, 65~88번째 글자에서 두 번 나타납니다.

예제 입력 4

aaaaaaa

예제 출력 4

3

aaa가 1~3번째, 4~6번째 글자에서 두 번 나타납니다.

W3sicHJvYmxlbV9pZCI6IjE3ODQ0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViY2Y1XHViZDk5XHVkNTU4XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3MjRcdWQ0NWNcdWIyOTQgXHViOWNjXHVjMGFjXHVhYzAwIFx1YWRjMFx1Y2MyZVx1Yzc0MCBcdWNlNWNcdWFkNmNcdWIyZTQuIFx1YWRmOFx1Yjc5OFx1YzExYyBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHVjNzg1XHViODI1XHVkNTYwIFx1YjU0YywgXHVjOTExXHViY2Y1XHViNDE4XHViMjk0IFx1YmQ4MFx1YmQ4NFx1Yzc3NCBcdWM3ODhcdWM3M2NcdWJhNzQsIFx1YzU1ZVx1YzExYyBcdWIwOThcdWM2MjggXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWJjZjVcdWMwYWNcdWQ1NzRcdWMxMWMgXHViZDk5XHVjNWVjXHViMTIzXHVjNWI0XHVjNTdjIFx1YjljOFx1Yzc0Y1x1Yzc3NCBcdWQzYjhcdWM1NDhcdWQ1NThcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzcyNFx1ZDQ1Y1x1YjI5NCBcdWI5ZTRcdWJjODggXHVjNzkwXHVjMmUwXHVjNzc0IFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWM5YzFcdWM4MTEgXHVhZTMwXHVjNWI1XHVkNTU4XHVjNWVjIFx1YmQ5OVx1YzVlY1x1YjEyM1x1YjJlNFx1YWMwMCwgXHViY2Y1XHVjMGFjXHViZDk5XHVjNWVjXHViMTIzXHVhZTMwXHViOTdjIFx1YjNjNFx1YzY0MFx1YzhmY1x1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHViOWNjXHViNGU0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1ZDU3NFx1YjJmOSBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM1ZDBcdWMxMWMgXHVhY2I5XHVjZTU4XHVjOWMwIFx1YzU0YVx1YWM4YyBcdWI0NTAgXHViYzg4IFx1Yzc3NFx1YzBjMSBcdWJjMThcdWJjZjVcdWI0MThcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YWUzNCBcdWJkODBcdWJkODQgXHViYjM4XHVjNzkwXHVjNWY0XHVhY2ZjIFx1ZDU3NFx1YjJmOSBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgMSBcdWM3NzRcdWMwYzEgMjAwLDAwMCBcdWM3NzRcdWQ1NThcdWM3NzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjOGZjXHVjNWI0XHVjOWM0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1YzVkMFx1YzExYyBcdWFjYjlcdWNlNThcdWM5YzAgXHVjNTRhXHVhYzhjIChkaXNqb2ludCkgXHViNDUwIFx1YmM4OCBcdWM3NzRcdWMwYzEgXHViNGYxXHVjN2E1XHVkNTU4XHViMjk0Jm5ic3A7XHVhYzAwXHVjN2E1IFx1YWUzNCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTgmbmJzcDtcdWFlMzhcdWM3NzRcdWI5N2MgXHVhY2Y1XHViYzMxXHVjNzQ0IFx1YWUzMFx1YzkwMFx1YzczY1x1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlOCwgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCZuYnNwO1x1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM1YzZcdWIyOTQgXHVhY2JkXHVjNmIwIC0xXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQiLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHA+YXBwbGVcdWM3NzQgMX41XHViYzg4XHVjOWY4LCZuYnNwOzE4fjIyXHViYzg4XHVjOWY4Jm5ic3A7XHVhZTAwXHVjNzkwXHVjNWQwXHVjMTFjJm5ic3A7XHViNDUwIFx1YmM4OCBcdWIwOThcdWQwYzBcdWIwYTlcdWIyYzhcdWIyZTQuPFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMiI6IjxwPlx1YmMxOFx1YmNmNVx1YjQxOFx1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQmbmJzcDtcdWM1YzZcdWMyYjVcdWIyYzhcdWIyZTQuPFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMyI6IjxwPnZ0emxkd2l5aWhwandzeGZkdmpoYmR1Ylx1YWMwMCAzMH41M1x1YmM4OFx1YzlmOCwgNjV+ODhcdWJjODhcdWM5ZjggXHVhZTAwXHVjNzkwXHVjNWQwXHVjMTFjIFx1YjQ1MCBcdWJjODggXHViMDk4XHVkMGMwXHViMGE5XHViMmM4XHViMmU0LjxcL3A+XHJcbiIsInNhbXBsZV9leHBsYWluXzQiOiI8cD5hYWFcdWFjMDAgMX4zXHViYzg4XHVjOWY4LCA0fjZcdWJjODhcdWM5ZjggXHVhZTAwXHVjNzkwXHVjNWQwXHVjMTFjIFx1YjQ1MCBcdWJjODggXHViMDk4XHVkMGMwXHViMGE5XHViMmM4XHViMmU0LjxcL3A+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjE3ODQ0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ3RybCAtIEMsIFYiLCJkZXNjcmlwdGlvbiI6IjxwPll1bnB5byBpcyBvbmUgb2YgdGhlIGxhenkgbWVuIGluIFVOSVNULiBUaHVzIEhlIGlzIGhhcHB5Jm5ic3A7d2hlbiBoZSBjYW4gaW5wdXQgc3RyaW5ncyB3aXRoIHRoZSBza2lsbCAmcXVvdDtDdHJsK0MmcXVvdDsgYW5kICZxdW90O0N0cmwrViZxdW90Oy48XC9wPlxyXG5cclxuPHA+SG93ZXZlciwgaGUgcmVhY2hlcyB0aGUgbGltaXQgb2YgaGlzIGJ1ZmZlciAoaW4gYnJhaW4pLiBTbyBoZSB3b3VsZCBsaWtlIHRvIHdyaXRlIGEgcHJvZ3JhbSB0byBuYXZpZ2F0ZSB0aGUgbG9uZ2VzdCBjb21tb24gc3RyaW5nLjxcL3A+XHJcblxyXG48cD5Ib3dldmVyLCBoZSByZWFjaGVzIHRoZSBsaW1pdCBvZiBoaXMgYnVmZmVyIChpbiBicmFpbikuIFNvIGhlIHdvdWxkIGxpa2UgdG8gd3JpdGUgYSBwcm9ncmFtIHRvIG5hdmlnYXRlIHRoZSBsb25nZXN0IGNvbW1vbiBzdHJpbmcuPFwvcD5cclxuXHJcbjxwPldyaXRlIHRoZSBwcm9ncmFtIHRoYXQgY2FuIG1ha2UgWXVucHlvIGhhcHB5LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+U3RyaW5nIHdpdGggbGVuZ3RoIEwgaXMgZ2l2ZW4uIHN0cmluZyBpcyBndWFyYW50ZWVkIHRvIGhvbGQgb25seSBsb3dlciBjYXNlIGNoYXJhY3RlcnMuIFRoZSBsZW5ndGggb2Ygc3RyaW5nIGlzIGJldHdlZW4gMSB0byAyMDAsMDAwLjxcL3A+XHJcblxyXG48cD5FYWNoIHN0cmluZyB3b3VsZCBjb250YWluIGF0IGxlYXN0IHR3byBraW5kIG9mIGxldHRlcnMuIGkuZS4gc3RyaW5nIHN1Y2ggYXMgJiMzOTthYWFhJiMzOTsgd2lsbCBub3QgZ2l2ZW4uPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHNob3VsZCBjb250YWluJm5ic3A7dGhlIGxlbmd0aCBvZiB0aGUgbG9uZ2VzdCBjb21tb24gc3RyaW5nLjxcL3A+XHJcblxyXG48cD5JZiB0aGVyZSBpcyBubyBjb21tb24gc3RyaW5nLCBvdXRwdXQgc2hvdWxkIGJlIC0xLjxcL3A+XHJcblxyXG48cD5UaGUgbG9uZ2VzdCBjb21tb24gc3RyaW5nJm5ic3A7YXJlIGRpc2pvaW50IGluIGdpdmVuIHN0cmluZy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQiLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHA+JnF1b3Q7YXBwbGUmcXVvdDsmbmJzcDtpcyB0aGUgbG9uZ2VzdCBjb21tb24gc3RyaW5nLjxcL3A+XHJcbiIsInNhbXBsZV9leHBsYWluXzIiOiI8cD5UaGVyZSBpcyBubyBjb21tb24gc3RyaW5nLjxcL3A+XHJcbiIsInNhbXBsZV9leHBsYWluXzMiOiI8cD4mcXVvdDt2dHpsZHdpeWlocGp3c3hmZHZqaGJkdWImcXVvdDsgaXMgdGhlIGxvbmdlc3QgY29tbW9uIHN0cmluZy48XC9wPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl80IjoiPHA+JnF1b3Q7YWFhJnF1b3Q7Jm5ic3A7IGlzIHRoZSBsb25nZXN0IGNvbW1vbiBzdHJpbmcuPFwvcD5cclxuIn1d