시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB87221937.255%

문제

문자열 A의 부분 문자열이란, A에 속하는 하나 또는 그 이상의 문자(연속하지 않아도 된다)를 이용해서 만든 새로운 문자열이다. 이때, A에서의 순서를 그대로 유지해야 된다.

두 문자열 A와 B가 주어진다. 이때, A의 부분 문자열이면서, B의 부분 문자열이 아닌 가장 짧은 부분 문자열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열 A, 둘째 줄에 문자열 B가 주어진다. 문자열은 알파벳 소문자로만 이루어져 있고, 길이는 2000보다 작거나 같다. 항상 정답이 존재하는 경우만 입력으로 주어진다. 

출력

첫째 줄에 A의 부분 문자열이면서, B의 부분 문자열이 아닌 가장 짧은 부분 문자열의 길이를 출력하고, 둘째 줄에는 문자열을 출력한다. 만약, 가능한 문자열이 여러 가지인 경우에는 아무거나 출력한다.

예제 입력 1

ababaa
abbaa

예제 출력 1

3
bab

예제 입력 2

babab
babba

예제 출력 2

3
aab

예제 입력 3

banana
anbnaanbaan

예제 출력 3

5
banna
W3sicHJvYmxlbV9pZCI6IjMyNDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI0NTAgXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNCAyIiwiZGVzY3JpcHRpb24iOiI8cD5cdWJiMzhcdWM3OTBcdWM1ZjQgQVx1Yzc1OCBcdWJkODBcdWJkODQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViNzgwLCBBXHVjNWQwIFx1YzE4ZFx1ZDU1OFx1YjI5NCBcdWQ1NThcdWIwOTggXHViNjEwXHViMjk0IFx1YWRmOCBcdWM3NzRcdWMwYzFcdWM3NTggXHViYjM4XHVjNzkwKFx1YzVmMFx1YzE4ZFx1ZDU1OFx1YzljMCBcdWM1NGFcdWM1NDRcdWIzYzQgXHViNDFjXHViMmU0KVx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NzRcdWMxMWMgXHViOWNjXHViNGUwIFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzRcdWIyZTQuIFx1Yzc3NFx1YjU0YywgQVx1YzVkMFx1YzExY1x1Yzc1OCBcdWMyMWNcdWMxMWNcdWI5N2MgXHVhZGY4XHViMzAwXHViODVjIFx1YzcyMFx1YzljMFx1ZDU3NFx1YzU3YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJiMzhcdWM3OTBcdWM1ZjQgQVx1YzY0MCBCXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHViNTRjLCBBXHVjNzU4IFx1YmQ4MFx1YmQ4NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzRcdWJhNzRcdWMxMWMsIEJcdWM3NTggXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM1NDRcdWIyY2MgXHVhYzAwXHVjN2E1IFx1YzllN1x1Yzc0MCBcdWJkODBcdWJkODQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJiMzhcdWM3OTBcdWM1ZjQgQSwgXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJiMzhcdWM3OTBcdWM1ZjQgQlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0MCBcdWM1NGNcdWQzMGNcdWJjYjMgXHVjMThjXHViYjM4XHVjNzkwXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YWUzOFx1Yzc3NFx1YjI5NCAyMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuIFx1ZDU2ZFx1YzBjMSBcdWM4MTVcdWIyZjVcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjljYyBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgQVx1Yzc1OCBcdWJkODBcdWJkODQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViYTc0XHVjMTFjLCBCXHVjNzU4IFx1YmQ4MFx1YmQ4NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YWMwMFx1YzdhNSBcdWM5ZTdcdWM3NDAgXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVhY2UwLCBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHVhYzAwXHViMmE1XHVkNTVjIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWM1NDRcdWJiMzRcdWFjNzBcdWIwOTggXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjMyNDQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUT0tJIiwiZGVzY3JpcHRpb24iOiI8cD5TdWJzdHJpbmcgb2Ygc29tZSBzdHJpbmcgQSBpcyBkZWZpbmVkIGFzIG9uZSBvZiBtb3JlIChub3QgbmVjZXNzYXJ5IHN1Y2NlZWRpbmcpIGVsZW1lbnRzIG9mIHRoZSBzdHJpbmcgd2l0aCBtYWludGFpbmluZyB0aGUgc2VxdWVuY2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZXJlIGFyZSBnaXZlbiB0d28gc3RyaW5ncywgc3RyaW5nIFZPS0kgYW5kIHN0cmluZyBUT0tJLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSB0aGUgcHJvZ3JhbSB0aGF0IHdpbGwgY2FsY3VsYXRlIGFueSBzaG9ydGVzdCBzdWJzdHJpbmcgb2Ygc3RyaW5nIFZPS0kgc3VjaCBhcyBpdCBpcyBub3Qgc3Vic3RyaW5nIG9mIHN0cmluZyBUT0tJLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW4gZmlyc3QgbGluZSBvZiBpbnB1dCBmaWxlIHRoZXJlIGlzIHN0cmluZyBWT0tJIGFuZCBpbiBzZWNvbmQgb25lIGlzIHN0cmluZyBUT0tJLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgb25seSBjaGFyYWN0ZXJzIHRoYXQgd2lsbCBvY2N1ciBhcmUgbG93ZXJjYXNlIGNoYXJhY3RlcnMgb2YgRW5nbGlzaCBhbHBoYWJldCAoJmxzcXVvO2EmcnNxdW87LSAmbHNxdW87eiZyc3F1bzspLiBTdHJpbmcgbGVuZ3RocyB3aWxsIGJlIGxlc3Mgb3IgZXF1YWwgdG8gMjAwMC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Tm90ZTogaW5wdXQgd2lsbCBiZSBzdWNoIHNvIHRoZXJlIHdpbGwgYWx3YXlzIGJlIGEgc29sdXRpb24uJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+SW4gdGhlIGZpcnN0IGxpbmUgb2YgZmlsZSB5b3Ugc2hvdWxkIHByaW50IHRoZSBsZW5ndGggb2Ygd2FudGVkIHN1YnN0cmluZywgYW5kIGluIHRoZSBzZWNvbmQgbGluZSB5b3Ugc2hvdWxkIHByaW50IGFueSB2YWxpZCBzdWJzdHJpbmcgZnJvbSB0aGUgdGV4dCBvZiB0aGUgcHJvYmxlbS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d