시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 3355 1351 997 43.863%

문제

두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오.

어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들어, 문자열 ABRACADABRA의 부분 문자열은 ABRA, RAC, D, ACADABRA, ABRACADABRA, 빈 문자열 등이다. 하지만, ABRC, RAA, BA, K는 부분 문자열이 아니다.

두 문자열 ABRACADABRA와 ECADADABRBCRDARA의 공통 부분 문자열은 CA, CADA, ADABR, 빈 문자열 등이 있다. 이 중에서 가장 긴 공통 부분 문자열은 ADABR이며, 길이는 5이다. 또, 두 문자열이 UPWJCIRUCAXIIRGL와 SBQNYBSBZDFNEV인 경우에는 가장 긴 공통 부분 문자열은 빈 문자열이다.

입력

첫째 줄과 둘째 줄에 문자열이 주어진다. 문자열은 대문자로 구성되어 있으며, 길이는 1 이상 4000 이하이다.

출력

첫째 줄에 두 문자열에 모두 포함 된 부분 문자열 중 가장 긴 것의 길이를 출력한다.

예제 입력 1

ABRACADABRA
ECADADABRBCRDARA

예제 출력 1

5
W3sicHJvYmxlbV9pZCI6IjU1ODIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjZjVcdWQxYjUgXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNCIsImRlc2NyaXB0aW9uIjoiPHA+XHViNDUwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWI0NTAgXHViYjM4XHVjNzkwXHVjNWY0XHVjNWQwIFx1YmFhOFx1YjQ1MCBcdWQzZWNcdWQ1NjhcdWI0MWMgXHVhYzAwXHVjN2E1IFx1YWUzNCBcdWFjZjVcdWQxYjUgXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWNjM2VcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHVjNWI0XHViNWE0IFx1YmIzOFx1Yzc5MFx1YzVmNCBzXHVjNzU4IFx1YmQ4MFx1YmQ4NCBcdWJiMzhcdWM3OTBcdWM1ZjQgdFx1Yjc4MCwgc1x1YzVkMCB0XHVhYzAwIFx1YzVmMFx1YzE4ZFx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwOThcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YjlkMFx1ZDU1Y1x1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHViYjM4XHVjNzkwXHVjNWY0IEFCUkFDQURBQlJBXHVjNzU4IFx1YmQ4MFx1YmQ4NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAgQUJSQSwgUkFDLCBELCBBQ0FEQUJSQSwgQUJSQUNBREFCUkEsIFx1YmU0OCBcdWJiMzhcdWM3OTBcdWM1ZjQgXHViNGYxXHVjNzc0XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIEFCUkMsIFJBQSwgQkEsIEtcdWIyOTQgXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM1NDRcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJiMzhcdWM3OTBcdWM1ZjQgQUJSQUNBREFCUkFcdWM2NDAgRUNBREFEQUJSQkNSREFSQVx1Yzc1OCBcdWFjZjVcdWQxYjUgXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0MCBDQSwgQ0FEQSwgQURBQlIsIFx1YmU0OCBcdWJiMzhcdWM3OTBcdWM1ZjQgXHViNGYxXHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YzkxMVx1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHVhZTM0IFx1YWNmNVx1ZDFiNSBcdWJkODBcdWJkODQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwIEFEQUJSXHVjNzc0XHViYTcwLCBcdWFlMzhcdWM3NzRcdWIyOTQgNVx1Yzc3NFx1YjJlNC4gXHViNjEwLCBcdWI0NTAgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFVQV0pDSVJVQ0FYSUlSR0xcdWM2NDAgU0JRTllCU0JaREZORVZcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YWMwMFx1YzdhNSBcdWFlMzQgXHVhY2Y1XHVkMWI1IFx1YmQ4MFx1YmQ4NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAgXHViZTQ4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWFjZmMgXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAgXHViMzAwXHViYjM4XHVjNzkwXHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxOFx1YzViNCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YWUzOFx1Yzc3NFx1YjI5NCAxIFx1Yzc3NFx1YzBjMSA0MDAwIFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjQ1MCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM1ZDAgXHViYWE4XHViNDUwIFx1ZDNlY1x1ZDU2OCBcdWI0MWMgXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNCBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1YWUzNCBcdWFjODNcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1NTgyIiwicHJvYmxlbV9sYW5nIjoiMiIsInRpdGxlIjoiXHU1MTcxXHU5MDFhXHU5MGU4XHU1MjA2XHU2NTg3XHU1YjU3XHU1MjE3IiwiZGVzY3JpcHRpb24iOiI8cD4yIFx1NTAwYlx1MzA2ZVx1NjU4N1x1NWI1N1x1NTIxN1x1MzA0Y1x1NGUwZVx1MzA0OFx1MzA4OVx1MzA4Y1x1MzA1Zlx1MzA2OFx1MzA0ZCwgXHU0ZTIxXHU2NWI5XHUzMDZlXHU2NTg3XHU1YjU3XHU1MjE3XHUzMDZiXHU1NDJiXHUzMDdlXHUzMDhjXHUzMDhiXHU2NTg3XHU1YjU3XHU1MjE3XHUzMDZlXHUzMDQ2XHUzMDYxXHU2NzAwXHUzMDgyXHU5NTc3XHUzMDQ0XHUzMDgyXHUzMDZlXHUzMDkyXHU2M2EyXHUzMDU3LCBcdTMwNWRcdTMwNmVcdTk1NzdcdTMwNTVcdTMwOTJcdTdiNTRcdTMwNDhcdTMwOGJcdTMwZDdcdTMwZWRcdTMwYjBcdTMwZTlcdTMwZTBcdTMwOTJcdTRmNWNcdTYyMTBcdTMwNWJcdTMwODguPFwvcD5cclxuXHJcbjxwPlx1MzA1M1x1MzA1M1x1MzA2NywgXHU2NTg3XHU1YjU3XHU1MjE3IHMgXHUzMDRjXHU2NTg3XHU1YjU3XHU1MjE3IHQgXHUzMDZiXHU1NDJiXHUzMDdlXHUzMDhjXHUzMDhiXHUzMDY4XHUzMDZmLCB0IFx1MzA2ZVx1NGUyZFx1MzA2YiBzIFx1MzA0Y1x1OTAyM1x1N2Q5YVx1MzA1N1x1MzA2Nlx1NzNmZVx1MzA4Y1x1MzA4Ylx1MzA1M1x1MzA2OFx1MzA5Mlx1MzA0NFx1MzA0Ni4gXHU3YTdhXHU2NTg3XHU1YjU3XHU1MjE3LCBcdTMwNTlcdTMwNmFcdTMwOGZcdTMwNjFcdTk1NzdcdTMwNTUgMCBcdTMwNmVcdTY1ODdcdTViNTdcdTUyMTdcdTMwNmYsIFx1MzA2OVx1MzA5M1x1MzA2YVx1NjU4N1x1NWI1N1x1NTIxN1x1MzA2Ylx1MzA4Mlx1NTQyYlx1MzA3ZVx1MzA4Y1x1MzA4Yi4gXHU0ZjhiXHUzMDQ4XHUzMDcwLCBcdTY1ODdcdTViNTdcdTUyMTcgQUJSQUNBREFCUkEgXHUzMDZiXHUzMDZmXHU2YjIxXHUzMDZlXHU2NTg3XHU1YjU3XHU1MjE3XHUzMDRjXHU1NDJiXHUzMDdlXHUzMDhjXHUzMDhiOiBBQlJBLCBSQUMsIEQsIEFDQURBQlJBLCBBQlJBQ0FEQUJSQSxcdTdhN2FcdTY1ODdcdTViNTdcdTUyMTdcdTMwNmFcdTMwNjkuIFx1NGUwMFx1NjViOSwgXHU2NTg3XHU1YjU3XHU1MjE3IEFCUkFDQURBQlJBIFx1MzA2Ylx1MzA2Zlx1NmIyMVx1MzA2ZVx1NjU4N1x1NWI1N1x1NTIxN1x1MzA2Zlx1NTQyYlx1MzA3ZVx1MzA4Y1x1MzA2YVx1MzA0NDogQUJSQywgUkFBLCBCQSwgSyBcdTMwNmFcdTMwNjkuPFwvcD5cclxuXHJcbjxwPlx1NGY4YiAxOiBcdTY1ODdcdTViNTdcdTUyMTdcdTMwNjhcdTMwNTdcdTMwNjYgQUJSQUNBREFCUkEgXHUzMDY4IEVDQURBREFCUkJDUkRBUkEgXHUzMDRjXHU0ZTBlXHUzMDQ4XHUzMDg5XHUzMDhjXHUzMDVmXHU1ODM0XHU1NDA4LCBcdTRlMjFcdTY1YjlcdTMwNmJcdTU0MmJcdTMwN2VcdTMwOGNcdTMwOGJcdTY1ODdcdTViNTdcdTUyMTdcdTMwNmJcdTMwNmYgQ0EgXHUzMDg0IENBREEgXHUzMDg0IEFEQUJSIFx1MzA4NFx1N2E3YVx1NjU4N1x1NWI1N1x1NTIxN1x1MzA2YVx1MzA2OVx1MzA0Y1x1MzA0Mlx1MzA4Yi4gXHUzMDVkXHUzMDZlXHUzMDQ2XHUzMDYxXHU2NzAwXHUzMDgyXHU5NTc3XHUzMDQ0XHUzMDZlXHUzMDZmIEFEQUJSIFx1MzA2N1x1MzA0Mlx1MzA4YSwgXHUzMDVkXHUzMDZlXHU5NTc3XHUzMDU1XHUzMDZmIDUgXHUzMDY3XHUzMDQyXHUzMDhiLiAyIFx1NTAwYlx1MzA2ZVx1NjU4N1x1NWI1N1x1NTIxN1x1MzA2ZVx1NGUyZFx1MzA2Ylx1NTQyYlx1MzA3ZVx1MzA4Y1x1MzA4YiBBREFCUlx1MzA2ZVx1NGY0ZFx1N2Y2ZVx1MzA5Mlx1NTZmMyAyLTEgXHUzMDZiXHU3OTNhXHUzMDU5LjxcL3A+XHJcblxyXG48cD5BQlJBQzx1PkFEQUJSPFwvdT5BPGJyIFwvPlxyXG5FQ0FEPHU+QURBQlI8XC91PkJDUkRBUkE8XC9wPlxyXG5cclxuPHA+XHU1NmYzIDItMSBcdTRmOGIgMSBcdTMwNmVcdTY1ODdcdTViNTdcdTUyMTdcdTMwNmVcdTRlMmRcdTMwNmJcdTczZmVcdTMwOGNcdTMwOGIgQURBQlIgXHUzMDZlXHU0ZjRkXHU3ZjZlPFwvcD5cclxuXHJcbjxwPlx1NGY4YiAyOiBcdTY1ODdcdTViNTdcdTUyMTdcdTMwNjhcdTMwNTdcdTMwNjYgVVBXSkNJUlVDQVhJSVJHTCBcdTMwNjggU0JRTllCU0JaREZORVYgXHUzMDRjXHU0ZTBlXHUzMDQ4XHUzMDg5XHUzMDhjXHUzMDVmXHU1ODM0XHU1NDA4LCBcdTRlMjFcdTY1YjlcdTMwNmJcdTU0MmJcdTMwN2VcdTMwOGNcdTMwOGJcdTY1ODdcdTViNTdcdTUyMTdcdTMwNmZcdTdhN2FcdTY1ODdcdTViNTdcdTUyMTdcdTMwNmVcdTMwN2ZcdTMwNjdcdTMwNDJcdTMwOGEsIFx1MzA1ZFx1MzA2ZVx1OTU3N1x1MzA1NVx1MzA2ZiAwIFx1MzA2N1x1MzA0Mlx1MzA4Yi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1NTE2NVx1NTI5Ylx1MzA2ZiAyIFx1ODg0Y1x1MzA0Ylx1MzA4OVx1MzA2YVx1MzA4YSwgMSBcdTg4NGNcdTc2ZWVcdTMwNmIgMSBcdTUwMGJcdTc2ZWVcdTMwNmVcdTY1ODdcdTViNTdcdTUyMTdcdTMwNGMsIDIgXHU4ODRjXHU3NmVlXHUzMDZiIDIgXHU1MDBiXHU3NmVlXHUzMDZlXHU2NTg3XHU1YjU3XHU1MjE3XHUzMDRjXHU0ZTBlXHUzMDQ4XHUzMDg5XHUzMDhjXHUzMDhiLiBcdTY1ODdcdTViNTdcdTUyMTdcdTMwNmZcdTgyZjFcdTU5MjdcdTY1ODdcdTViNTdcdTMwNGJcdTMwODlcdTMwNmFcdTMwOGEsIFx1NTQwNFx1MzAwNVx1MzA2ZVx1NjU4N1x1NWI1N1x1NTIxN1x1MzA2ZVx1OTU3N1x1MzA1NVx1MzA2ZiAxIFx1NGVlNVx1NGUwYSA0MDAwIFx1NGVlNVx1NGUwYlx1MzA2N1x1MzA0Mlx1MzA4Yi48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHU1MWZhXHU1MjliXHUzMDZmXHVmZjBjXHU0ZTBlXHUzMDQ4XHUzMDg5XHUzMDhjXHUzMDVmIDIgXHU1MDBiXHUzMDZlXHU2NTg3XHU1YjU3XHU1MjE3XHUzMDZlXHU0ZTIxXHU2NWI5XHUzMDZiXHU1NDJiXHUzMDdlXHUzMDhjXHUzMDhiXHU2NTg3XHU1YjU3XHU1MjE3XHUzMDZlXHUzMDQ2XHUzMDYxXHU2NzAwXHUzMDgyXHU5NTc3XHUzMDQ0XHUzMDgyXHUzMDZlXHUzMDZlXHU5NTc3XHUzMDU1XHUzMDYwXHUzMDUxXHUzMDkyXHU1NDJiXHUzMDgwIDEgXHU4ODRjXHUzMDRiXHUzMDg5XHUzMDZhXHUzMDhiXHVmZjBlPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNzdjXHViY2Y4XHVjNWI0In1d

출처

Olympiad > 일본정보올림피아드 > JOI 2008 2번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: scka