시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 9222 3784 2918 43.352%

문제

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

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

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

입력

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

출력

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

예제 입력 1

ABRACADABRA
ECADADABRBCRDARA

예제 출력 1

5

예제 입력 2

UPWJCIRUCAXIIRGL
SBQNYBSBZDFNEV

예제 출력 2

0
W3sicHJvYmxlbV9pZCI6IjU1ODIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjZjVcdWQxYjUgXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNCIsImRlc2NyaXB0aW9uIjoiPHA+XHViNDUwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWI0NTAgXHViYjM4XHVjNzkwXHVjNWY0XHVjNWQwIFx1YmFhOFx1YjQ1MCBcdWQzZWNcdWQ1NjhcdWI0MWMgXHVhYzAwXHVjN2E1IFx1YWUzNCBcdWFjZjVcdWQxYjUgXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWNjM2VcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHVjNWI0XHViNWE0IFx1YmIzOFx1Yzc5MFx1YzVmNCBzXHVjNzU4IFx1YmQ4MFx1YmQ4NCBcdWJiMzhcdWM3OTBcdWM1ZjQgdFx1Yjc4MCwgc1x1YzVkMCB0XHVhYzAwIFx1YzVmMFx1YzE4ZFx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwOThcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YjlkMFx1ZDU1Y1x1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHViYjM4XHVjNzkwXHVjNWY0IDxjb2RlPkFCUkFDQURBQlJBPFwvY29kZT5cdWM3NTggXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0MCA8Y29kZT5BQlJBPFwvY29kZT4sIDxjb2RlPlJBQzxcL2NvZGU+LCA8Y29kZT5EPFwvY29kZT4sIDxjb2RlPkFDQURBQlJBPFwvY29kZT4sIDxjb2RlPkFCUkFDQURBQlJBPFwvY29kZT4sIFx1YmU0OCBcdWJiMzhcdWM3OTBcdWM1ZjQgXHViNGYxXHVjNzc0XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIDxjb2RlPkFCUkM8XC9jb2RlPiwgPGNvZGU+UkFBPFwvY29kZT4sIDxjb2RlPkJBPFwvY29kZT4sIDxjb2RlPks8XC9jb2RlPlx1YjI5NCBcdWJkODBcdWJkODQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzU0NFx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmIzOFx1Yzc5MFx1YzVmNCA8Y29kZT5BQlJBQ0FEQUJSQTxcL2NvZGU+XHVjNjQwIDxjb2RlPkVDQURBREFCUkJDUkRBUkE8XC9jb2RlPlx1Yzc1OCBcdWFjZjVcdWQxYjUgXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0MCA8Y29kZT5DQTxcL2NvZGU+LCA8Y29kZT5DQURBPFwvY29kZT4sIDxjb2RlPkFEQUJSPFwvY29kZT4sIFx1YmU0OCBcdWJiMzhcdWM3OTBcdWM1ZjQgXHViNGYxXHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YzkxMVx1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHVhZTM0IFx1YWNmNVx1ZDFiNSBcdWJkODBcdWJkODQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwIDxjb2RlPkFEQUJSPFwvY29kZT5cdWM3NzRcdWJhNzAsIFx1YWUzOFx1Yzc3NFx1YjI5NCA1XHVjNzc0XHViMmU0LiBcdWI2MTAsIFx1YjQ1MCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgPGNvZGU+VVBXSkNJUlVDQVhJSVJHTDxcL2NvZGU+XHVjNjQwIDxjb2RlPlNCUU5ZQlNCWkRGTkVWPFwvY29kZT5cdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YWMwMFx1YzdhNSBcdWFlMzQgXHVhY2Y1XHVkMWI1IFx1YmQ4MFx1YmQ4NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAgXHViZTQ4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWFjZmMgXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAgXHViMzAwXHViYjM4XHVjNzkwXHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxOFx1YzViNCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YWUzOFx1Yzc3NFx1YjI5NCAxIFx1Yzc3NFx1YzBjMSA0MDAwIFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjQ1MCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM1ZDAgXHViYWE4XHViNDUwIFx1ZDNlY1x1ZDU2OCBcdWI0MWMgXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNCBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1YWUzNCBcdWFjODNcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI1NTgyIiwicHJvYmxlbV9sYW5nIjoiMiIsInRpdGxlIjoiXHU1MTcxXHU5MDFhXHU5MGU4XHU1MjA2XHU2NTg3XHU1YjU3XHU1MjE3IiwiZGVzY3JpcHRpb24iOiI8cD4yIFx1NTAwYlx1MzA2ZVx1NjU4N1x1NWI1N1x1NTIxN1x1MzA0Y1x1NGUwZVx1MzA0OFx1MzA4OVx1MzA4Y1x1MzA1Zlx1MzA2OFx1MzA0ZCwgXHU0ZTIxXHU2NWI5XHUzMDZlXHU2NTg3XHU1YjU3XHU1MjE3XHUzMDZiXHU1NDJiXHUzMDdlXHUzMDhjXHUzMDhiXHU2NTg3XHU1YjU3XHU1MjE3XHUzMDZlXHUzMDQ2XHUzMDYxXHU2NzAwXHUzMDgyXHU5NTc3XHUzMDQ0XHUzMDgyXHUzMDZlXHUzMDkyXHU2M2EyXHUzMDU3LCBcdTMwNWRcdTMwNmVcdTk1NzdcdTMwNTVcdTMwOTJcdTdiNTRcdTMwNDhcdTMwOGJcdTMwZDdcdTMwZWRcdTMwYjBcdTMwZTlcdTMwZTBcdTMwOTJcdTRmNWNcdTYyMTBcdTMwNWJcdTMwODguPFwvcD5cclxuXHJcbjxwPlx1MzA1M1x1MzA1M1x1MzA2NywgXHU2NTg3XHU1YjU3XHU1MjE3IHMgXHUzMDRjXHU2NTg3XHU1YjU3XHU1MjE3IHQgXHUzMDZiXHU1NDJiXHUzMDdlXHUzMDhjXHUzMDhiXHUzMDY4XHUzMDZmLCB0IFx1MzA2ZVx1NGUyZFx1MzA2YiBzIFx1MzA0Y1x1OTAyM1x1N2Q5YVx1MzA1N1x1MzA2Nlx1NzNmZVx1MzA4Y1x1MzA4Ylx1MzA1M1x1MzA2OFx1MzA5Mlx1MzA0NFx1MzA0Ni4gXHU3YTdhXHU2NTg3XHU1YjU3XHU1MjE3LCBcdTMwNTlcdTMwNmFcdTMwOGZcdTMwNjFcdTk1NzdcdTMwNTUgMCBcdTMwNmVcdTY1ODdcdTViNTdcdTUyMTdcdTMwNmYsIFx1MzA2OVx1MzA5M1x1MzA2YVx1NjU4N1x1NWI1N1x1NTIxN1x1MzA2Ylx1MzA4Mlx1NTQyYlx1MzA3ZVx1MzA4Y1x1MzA4Yi4gXHU0ZjhiXHUzMDQ4XHUzMDcwLCBcdTY1ODdcdTViNTdcdTUyMTcgPGNvZGU+QUJSQUNBREFCUkE8XC9jb2RlPiBcdTMwNmJcdTMwNmZcdTZiMjFcdTMwNmVcdTY1ODdcdTViNTdcdTUyMTdcdTMwNGNcdTU0MmJcdTMwN2VcdTMwOGNcdTMwOGI6IDxjb2RlPkFCUkE8XC9jb2RlPiwgPGNvZGU+UkFDPFwvY29kZT4sIDxjb2RlPkQ8XC9jb2RlPiwgPGNvZGU+QUNBREFCUkE8XC9jb2RlPiwgPGNvZGU+QUJSQUNBREFCUkE8XC9jb2RlPixcdTdhN2FcdTY1ODdcdTViNTdcdTUyMTdcdTMwNmFcdTMwNjkuIFx1NGUwMFx1NjViOSwgXHU2NTg3XHU1YjU3XHU1MjE3IDxjb2RlPkFCUkFDQURBQlJBPFwvY29kZT4gXHUzMDZiXHUzMDZmXHU2YjIxXHUzMDZlXHU2NTg3XHU1YjU3XHU1MjE3XHUzMDZmXHU1NDJiXHUzMDdlXHUzMDhjXHUzMDZhXHUzMDQ0OiA8Y29kZT5BQlJDPFwvY29kZT4sIDxjb2RlPlJBQTxcL2NvZGU+LCA8Y29kZT5CQTxcL2NvZGU+LCA8Y29kZT5LPFwvY29kZT4gXHUzMDZhXHUzMDY5LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHU1MTY1XHU1MjliXHUzMDZmIDIgXHU4ODRjXHUzMDRiXHUzMDg5XHUzMDZhXHUzMDhhLCAxIFx1ODg0Y1x1NzZlZVx1MzA2YiAxIFx1NTAwYlx1NzZlZVx1MzA2ZVx1NjU4N1x1NWI1N1x1NTIxN1x1MzA0YywgMiBcdTg4NGNcdTc2ZWVcdTMwNmIgMiBcdTUwMGJcdTc2ZWVcdTMwNmVcdTY1ODdcdTViNTdcdTUyMTdcdTMwNGNcdTRlMGVcdTMwNDhcdTMwODlcdTMwOGNcdTMwOGIuIFx1NjU4N1x1NWI1N1x1NTIxN1x1MzA2Zlx1ODJmMVx1NTkyN1x1NjU4N1x1NWI1N1x1MzA0Ylx1MzA4OVx1MzA2YVx1MzA4YSwgXHU1NDA0XHUzMDA1XHUzMDZlXHU2NTg3XHU1YjU3XHU1MjE3XHUzMDZlXHU5NTc3XHUzMDU1XHUzMDZmIDEgXHU0ZWU1XHU0ZTBhIDQwMDAgXHU0ZWU1XHU0ZTBiXHUzMDY3XHUzMDQyXHUzMDhiLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1NTFmYVx1NTI5Ylx1MzA2Zlx1ZmYwY1x1NGUwZVx1MzA0OFx1MzA4OVx1MzA4Y1x1MzA1ZiAyIFx1NTAwYlx1MzA2ZVx1NjU4N1x1NWI1N1x1NTIxN1x1MzA2ZVx1NGUyMVx1NjViOVx1MzA2Ylx1NTQyYlx1MzA3ZVx1MzA4Y1x1MzA4Ylx1NjU4N1x1NWI1N1x1NTIxN1x1MzA2ZVx1MzA0Nlx1MzA2MVx1NjcwMFx1MzA4Mlx1OTU3N1x1MzA0NFx1MzA4Mlx1MzA2ZVx1MzA2ZVx1OTU3N1x1MzA1NVx1MzA2MFx1MzA1MVx1MzA5Mlx1NTQyYlx1MzA4MCAxIFx1ODg0Y1x1MzA0Ylx1MzA4OVx1MzA2YVx1MzA4Ylx1ZmYwZTxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdTRmOGIgMTogXHU2NTg3XHU1YjU3XHU1MjE3XHUzMDY4XHUzMDU3XHUzMDY2IDxjb2RlPkFCUkFDQURBQlJBPFwvY29kZT4gXHUzMDY4IDxjb2RlPkVDQURBREFCUkJDUkRBUkE8XC9jb2RlPiBcdTMwNGNcdTRlMGVcdTMwNDhcdTMwODlcdTMwOGNcdTMwNWZcdTU4MzRcdTU0MDgsIFx1NGUyMVx1NjViOVx1MzA2Ylx1NTQyYlx1MzA3ZVx1MzA4Y1x1MzA4Ylx1NjU4N1x1NWI1N1x1NTIxN1x1MzA2Ylx1MzA2ZiA8Y29kZT5DQTxcL2NvZGU+IFx1MzA4NCA8Y29kZT5DQURBPFwvY29kZT4gXHUzMDg0IDxjb2RlPkFEQUJSPFwvY29kZT4gXHUzMDg0XHU3YTdhXHU2NTg3XHU1YjU3XHU1MjE3XHUzMDZhXHUzMDY5XHUzMDRjXHUzMDQyXHUzMDhiLiBcdTMwNWRcdTMwNmVcdTMwNDZcdTMwNjFcdTY3MDBcdTMwODJcdTk1NzdcdTMwNDRcdTMwNmVcdTMwNmYgPGNvZGU+QURBQlI8XC9jb2RlPiBcdTMwNjdcdTMwNDJcdTMwOGEsIFx1MzA1ZFx1MzA2ZVx1OTU3N1x1MzA1NVx1MzA2ZiA1IFx1MzA2N1x1MzA0Mlx1MzA4Yi4gMiBcdTUwMGJcdTMwNmVcdTY1ODdcdTViNTdcdTUyMTdcdTMwNmVcdTRlMmRcdTMwNmJcdTU0MmJcdTMwN2VcdTMwOGNcdTMwOGIgPGNvZGU+QURBQlI8XC9jb2RlPlx1MzA2ZVx1NGY0ZFx1N2Y2ZVx1MzA5Mlx1NTZmMyAyLTEgXHUzMDZiXHU3OTNhXHUzMDU5LjxcL3A+XHJcblxyXG48cHJlPlxyXG5BQlJBQzx1PkFEQUJSPFwvdT5BXHJcbkVDQUQ8dT5BREFCUjxcL3U+QkNSREFSQTxcL3ByZT5cclxuXHJcbjxwPlx1NTZmMyAyLTEgXHU0ZjhiIDEgXHUzMDZlXHU2NTg3XHU1YjU3XHU1MjE3XHUzMDZlXHU0ZTJkXHUzMDZiXHU3M2ZlXHUzMDhjXHUzMDhiIDxjb2RlPkFEQUJSPFwvY29kZT4gXHUzMDZlXHU0ZjRkXHU3ZjZlPFwvcD5cclxuXHJcbjxwPlx1NGY4YiAyOiBcdTY1ODdcdTViNTdcdTUyMTdcdTMwNjhcdTMwNTdcdTMwNjYgPGNvZGU+VVBXSkNJUlVDQVhJSVJHTDxcL2NvZGU+IFx1MzA2OCA8Y29kZT5TQlFOWUJTQlpERk5FVjxcL2NvZGU+IFx1MzA0Y1x1NGUwZVx1MzA0OFx1MzA4OVx1MzA4Y1x1MzA1Zlx1NTgzNFx1NTQwOCwgXHU0ZTIxXHU2NWI5XHUzMDZiXHU1NDJiXHUzMDdlXHUzMDhjXHUzMDhiXHU2NTg3XHU1YjU3XHU1MjE3XHUzMDZmXHU3YTdhXHU2NTg3XHU1YjU3XHU1MjE3XHUzMDZlXHUzMDdmXHUzMDY3XHUzMDQyXHUzMDhhLCBcdTMwNWRcdTMwNmVcdTk1NzdcdTMwNTVcdTMwNmYgMCBcdTMwNjdcdTMwNDJcdTMwOGIuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJKYXBhbmVzZSJ9XQ==

출처

Olympiad > Japanese Olympiad in Informatics > JOI 2008 2번

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