시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 27 12 11 68.750%

문제

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

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

입력

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

출력

첫째 줄에 A의 부분 문자열이면서, B의 부분 문자열이 아닌 가장 짧은 부분 문자열의 길이를 출력한다.

예제 입력 1

ababaa
abbaa

예제 출력 1

3
W3sicHJvYmxlbV9pZCI6IjIxMTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI0NTAgXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNCIsImRlc2NyaXB0aW9uIjoiPHA+XHViYjM4XHVjNzkwXHVjNWY0IEFcdWM3NTggXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1Yjc4MCwgQVx1YzVkMCBcdWMxOGRcdWQ1NThcdWIyOTQgXHVkNTU4XHViMDk4IFx1YjYxMFx1YjI5NCBcdWFkZjggXHVjNzc0XHVjMGMxXHVjNzU4IFx1YmIzOFx1Yzc5MChcdWM1ZjBcdWMxOGRcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNTQ0XHViM2M0IFx1YjQxY1x1YjJlNClcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1YjljY1x1YjRlMCBcdWMwYzhcdWI4NWNcdWM2YjQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViMmU0LiBcdWM3NzRcdWI1NGMsIEFcdWM1ZDBcdWMxMWNcdWM3NTggXHVjMjFjXHVjMTFjXHViOTdjIFx1YWRmOFx1YjMwMFx1Yjg1YyBcdWM3MjBcdWM5YzBcdWQ1NzRcdWM1N2MgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHViYjM4XHVjNzkwXHVjNWY0IEFcdWM2NDAgQlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjU0YywgQVx1Yzc1OCBcdWJkODBcdWJkODQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViYTc0XHVjMTFjLCBCXHVjNzU4IFx1YmQ4MFx1YmQ4NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YWMwMFx1YzdhNSBcdWM5ZTdcdWM3NDAgXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViYjM4XHVjNzkwXHVjNWY0IEEsIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViYjM4XHVjNzkwXHVjNWY0IEJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAgXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWFlMzhcdWM3NzRcdWIyOTQgMTAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHViMmU0LiBcdWQ1NmRcdWMwYzEgXHVjODE1XHViMmY1XHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWI5Y2MgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIEFcdWM3NTggXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1YmE3NFx1YzExYywgQlx1Yzc1OCBcdWJkODBcdWJkODQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzU0NFx1YjJjYyBcdWFjMDBcdWM3YTUgXHVjOWU3XHVjNzQwIFx1YmQ4MFx1YmQ4NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyMTEyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVk9LSSIsImRlc2NyaXB0aW9uIjoiPHA+U3Vic3RyaW5nIG9mIHNvbWUgc3RyaW5nIEEgaXMgZGVmaW5lZCBhcyBvbmUgb3IgbW9yZSAobm90IG5lY2Vzc2FyeSBzdWNjZWVkaW5nKSBlbGVtZW50cyBvZiB0aGUgc3RyaW5nIHdpdGggbWFpbnRhaW5pbmcgdGhlIHNlcXVlbmNlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGVyZSBhcmUgZ2l2ZW4gdHdvIHN0cmluZ3MsIHN0cmluZyBWT0tJIGFuZCBzdHJpbmcgVE9LSS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgdGhlIHByb2dyYW0gdGhhdCB3aWxsIGNhbGN1bGF0ZSB0aGUgbGVuZ3RoIG9mIGFueSBzaG9ydGVzdCBzdWJzdHJpbmcgb2Ygc3RyaW5nIFZPS0kgc3VjaCBhcyBpdCBpcyBub3Qgc3Vic3RyaW5nIG9mIHN0cmluZyBUT0tJLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW4gZmlyc3QgbGluZSBvZiBpbnB1dCBmaWxlIHRoZXJlIGlzIHN0cmluZyBWT0tJIGFuZCBpbiBzZWNvbmQgb25lIGlzIHN0cmluZyBUT0tJLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgb25seSBjaGFyYWN0ZXJzIHRoYXQgd2lsbCBvY2N1ciBhcmUgbG93ZXJjYXNlIGNoYXJhY3RlcnMgb2YgRW5nbGlzaCBhbHBoYWJldCAoJmxzcXVvO2EmcnNxdW87LSAmbHNxdW87eiZyc3F1bzspLiBTdHJpbmcgbGVuZ3RocyB3aWxsIGJlIGxlc3Mgb3IgZXF1YWwgdG8gMTAwMC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Tm90ZTogaW5wdXQgZGF0YSB3aWxsIGJlIHN1Y2ggc28gdGhlcmUgd2lsbCBhbHdheXMgYmUgYSBzb2x1dGlvbi4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5JbiB0aGUgZmlyc3QgbGluZSBvZiBmaWxlIHlvdSBzaG91bGQgcHJpbnQgdGhlIGxlbmd0aCBvZiB3YW50ZWQgc3Vic3RyaW5nLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=