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

문제

알파벳 소문자로 되어있는 두 문자열 a와 b가 주어졌을 때, ax 또는 bx가 팰린드롬이 되는 가장 짧은 문자열 x를 찾는 프로그램을 작성하시오. 이때, ax와 bx가 둘 다 팰린드롬이면 안 된다. 

입력

입력은 여러개의 테스트 케이스로 되어 있다. 각 테스트 케이스는 두 줄이고, 첫째 줄에는 a, 둘째 줄에는 b가 주어진다. 각 문자열은 0개 이상, 1,000개 이하의 알파벳 소문자로 이루어져 있다.

출력

각 테스트 케이스에 대해서 문제의 조건을 만족하는 가장 짧은 x를 출력한다. 만약 그러한 x가 여러개라면 사전순으로 가장 앞서는 것을 출력한다. 조건을 만족하는 문자열이 없는 경우 "No Solution."을 출력한다.

예제 입력 1

abab
ababab
abc
def

예제 출력 1

baba
ba
W3sicHJvYmxlbV9pZCI6IjQzOTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwNWRcdWM3NzhcdWI0ZGNcdWI4NmMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWMxOGNcdWJiMzhcdWM3OTBcdWI4NWMgXHViNDE4XHVjNWI0XHVjNzg4XHViMjk0IFx1YjQ1MCBcdWJiMzhcdWM3OTBcdWM1ZjQgYVx1YzY0MCBiXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIGF4IFx1YjYxMFx1YjI5NCBieFx1YWMwMCBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmNcdWM3NzQgXHViNDE4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWM5ZTdcdWM3NDAgXHViYjM4XHVjNzkwXHVjNWY0IHhcdWI5N2MgXHVjYzNlXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1Yzc3NFx1YjU0YywgYXhcdWM2NDAgYnhcdWFjMDAgXHViNDU4IFx1YjJlNCBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmNcdWM3NzRcdWJhNzQgXHVjNTQ4IFx1YjQxY1x1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWNcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWI0NTAgXHVjOTA0XHVjNzc0XHVhY2UwLCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IGEsIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgYlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAgMFx1YWMxYyBcdWM3NzRcdWMwYzEsIDEsMDAwXHVhYzFjIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWM1NGNcdWQzMGNcdWJjYjMgXHVjMThjXHViYjM4XHVjNzkwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1YmIzOFx1YzgxY1x1Yzc1OCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWM5ZTdcdWM3NDAgeFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWFkZjhcdWI3ZWNcdWQ1NWMgeFx1YWMwMCBcdWM1ZWNcdWI3ZWNcdWFjMWNcdWI3N2NcdWJhNzQgXHVjMGFjXHVjODA0XHVjMjFjXHVjNzNjXHViODVjIFx1YWMwMFx1YzdhNSBcdWM1NWVcdWMxMWNcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjNWM2XHViMjk0IFx1YWNiZFx1YzZiMCAmcXVvdDtObyBTb2x1dGlvbi4mcXVvdDtcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjQzOTkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTdWZmaWRyb21lcyIsImRlc2NyaXB0aW9uIjoiPHA+R2l2ZW4gdHdvIHN0cmluZ3Mgb2YgbG93ZXJjYXNlIGxldHRlcnMsIGEgYW5kIGIsIHByaW50IHRoZSBzaG9ydGVzdCBzdHJpbmcgeCBvZiBsb3dlcmNhc2UgbGV0dGVycyBzdWNoIHRoYXQgZXhhY3RseSBvbmUgKGJ1dCBub3QgYm90aCkgb2YgYXggb3IgYnggaXMgYSBwYWxpbmRyb21lOyB0aGF0IGlzLCBlcXVhbCB0byBpdHNlbGYgd2hlbiByZXZlcnNlZC4gU3RhbmRhcmQgaW5wdXQgY29udGFpbnMgc2V2ZXJhbCBwYWlycyBvZiBhIGFuZCBiLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+RWFjaCBzdHJpbmcgaXMgb24gYSBzZXBhcmF0ZSBsaW5lIGFuZCBjb25zaXN0cyBvZiBiZXR3ZWVuIDAgYW5kIDEsMDAwIGxvd2VyY2FzZSBsZXR0ZXJzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHBhaXIsIG91dHB1dCBhIGxpbmUgY29udGFpbmluZyB4LiBJZiBzZXZlcmFsIHggc2F0aXNmeSB0aGUgY3JpdGVyaWEgYWJvdmUsIGNob29zZSB0aGUgZmlyc3Qgb25lIGluIGFscGhhYmV0aWNhbCBvcmRlci4mbmJzcDtJZiB0aGVyZSBpcyBubyBzdWNoIHN0cmluZyB4LCBvdXRwdXQgJnF1b3Q7Tm8gU29sdXRpb24uJnF1b3Q7LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Contest > Waterloo's local Programming Contests > 2 October, 1999 D번