시간 제한메모리 제한제출정답맞힌 사람정답 비율
8 초 16 MB311674221.429%

문제

문자열이 주어졌을 때, 이 문자열을 다른 문자열로 바꾸는 편집 스크립트를 작성하려고 한다. 편집 스크립트에서 사용할 수 있는 명령은 아래와 같이 총 네 가지가 있다.

  • 추가 ('a'): 한 글자를 출력한다. 이 명령은 입력 문자열을 건드리지 않는다.
  • 삭제 ('d'): 한 글자를 삭제한다. 이 명령은 입력 문자열에서 맨 앞 글자를 삭제하고, 아무것도 출력하지 않는다.
  • 수정 ('m'): 한 글자를 수정한다. 즉, 입력 문자열에서 맨 앞 글자를 삭제하고, 바꾼 글자를 출력한다.
  • 복사 ('c'): 한 글자를 복사한다. 입력에서 맨 앞 글자를 삭제하고, 삭제한 그 글자를 출력한다.

가장 짧은 편집 스크립트란, 추가, 삭제, 수정을 가장 적게 사용한 스크립트이다.

두 문자열이 주어졌을 때, 첫 번째 문자열을 두 번째 문자열로 바꾸는 가장 짧은 편집 스크립트를 작성하는 프로그램을 작성하시오. 

입력

두 문자열이 한 줄에 하나씩 주어진다. 각 문자열은 영문알파벳과 숫자로만 이루어져 있으며, 길이는 1보다 크거나 같고, 17000보다 작거나 같다.

출력

가장 짧은 편집 스크립트를 출력한다. 한 명령을 한 줄에 하나씩 출력하며, 문제의 괄호에 나와있는 (a, d, m, c)중 하나를 출력하고, 그 명령을 수행하는데 사용한 글자를 출력한다. (출력할 글자나 삭제할 글자)

가장 짧은 편집 스크립트가 여러 가지인 경우에는 아무거나 출력하면 된다.

예제 입력 1

abcde
xabzdey

예제 출력 1

a x
c a
c b
m z
c d
c e
a y
W3sicHJvYmxlbV9pZCI6IjE3MTYxIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkM2I4XHVjOWQxIFx1YWM3MFx1YjlhYyAoSGFyZCkiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3NzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1YjJlNFx1Yjk3OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWI4NWMgXHViYzE0XHVhZmI4XHViMjk0IFx1ZDNiOFx1YzlkMSBcdWMyYTRcdWQwNmNcdWI5YmRcdWQyYjhcdWI5N2MgXHVjNzkxXHVjMTMxXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVkM2I4XHVjOWQxIFx1YzJhNFx1ZDA2Y1x1YjliZFx1ZDJiOFx1YzVkMFx1YzExYyBcdWMwYWNcdWM2YTlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJhODVcdWI4MzlcdWM3NDAgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWNkMWQgXHViMTI0IFx1YWMwMFx1YzljMFx1YWMwMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVjZDk0XHVhYzAwICgmIzM5O2EmIzM5Oyk6IFx1ZDU1YyBcdWFlMDBcdWM3OTBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM3NzQgXHViYTg1XHViODM5XHVjNzQwIFx1Yzc4NVx1YjgyNSBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHVhYzc0XHViNGRjXHViOWFjXHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjMGFkXHVjODFjICgmIzM5O2QmIzM5Oyk6IFx1ZDU1YyBcdWFlMDBcdWM3OTBcdWI5N2MgXHVjMGFkXHVjODFjXHVkNTVjXHViMmU0LiBcdWM3NzQgXHViYTg1XHViODM5XHVjNzQwIFx1Yzc4NVx1YjgyNSBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM1ZDBcdWMxMWMgXHViOWU4IFx1YzU1ZSBcdWFlMDBcdWM3OTBcdWI5N2MgXHVjMGFkXHVjODFjXHVkNTU4XHVhY2UwLCBcdWM1NDRcdWJiMzRcdWFjODNcdWIzYzQgXHVjZDljXHViODI1XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjMjE4XHVjODE1ICgmIzM5O20mIzM5Oyk6IFx1ZDU1YyBcdWFlMDBcdWM3OTBcdWI5N2MgXHVjMjE4XHVjODE1XHVkNTVjXHViMmU0LiBcdWM5ODksIFx1Yzc4NVx1YjgyNSBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM1ZDBcdWMxMWMgXHViOWU4IFx1YzU1ZSBcdWFlMDBcdWM3OTBcdWI5N2MgXHVjMGFkXHVjODFjXHVkNTU4XHVhY2UwLCBcdWJjMTRcdWFmYmMgXHVhZTAwXHVjNzkwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViY2Y1XHVjMGFjICgmIzM5O2MmIzM5Oyk6IFx1ZDU1YyBcdWFlMDBcdWM3OTBcdWI5N2MgXHViY2Y1XHVjMGFjXHVkNTVjXHViMmU0LiBcdWM3ODVcdWI4MjVcdWM1ZDBcdWMxMWMgXHViOWU4IFx1YzU1ZSBcdWFlMDBcdWM3OTBcdWI5N2MgXHVjMGFkXHVjODFjXHVkNTU4XHVhY2UwLCBcdWMwYWRcdWM4MWNcdWQ1NWMgXHVhZGY4IFx1YWUwMFx1Yzc5MFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVhYzAwXHVjN2E1IFx1YzllN1x1Yzc0MCBcdWQzYjhcdWM5ZDEgXHVjMmE0XHVkMDZjXHViOWJkXHVkMmI4XHViNzgwLCBcdWNkOTRcdWFjMDAsIFx1YzBhZFx1YzgxYywgXHVjMjE4XHVjODE1XHVjNzQ0IFx1YWMwMFx1YzdhNSBcdWM4MDFcdWFjOGMgXHVjMGFjXHVjNmE5XHVkNTVjIFx1YzJhNFx1ZDA2Y1x1YjliZFx1ZDJiOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yjg1YyBcdWJjMTRcdWFmYjhcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YzllN1x1Yzc0MCBcdWQzYjhcdWM5ZDEgXHVjMmE0XHVkMDZjXHViOWJkXHVkMmI4XHViOTdjIFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHViNDUwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAgXHVjNjAxXHViYjM4XHVjNTRjXHVkMzBjXHViY2IzXHVhY2ZjIFx1YzIyYlx1Yzc5MFx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWFlMzhcdWM3NzRcdWIyOTQgMVx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCAxNzAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMFx1YzdhNSBcdWM5ZTdcdWM3NDAgXHVkM2I4XHVjOWQxIFx1YzJhNFx1ZDA2Y1x1YjliZFx1ZDJiOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1ZDU1YyBcdWJhODVcdWI4MzlcdWM3NDQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjZDljXHViODI1XHVkNTU4XHViYTcwLCBcdWJiMzhcdWM4MWNcdWM3NTggXHVhZDA0XHVkNjM4XHVjNWQwIFx1YjA5OFx1YzY0MFx1Yzc4OFx1YjI5NCAoYSwgZCwgbSwgYylcdWM5MTEgXHVkNTU4XHViMDk4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YWNlMCwgXHVhZGY4IFx1YmE4NVx1YjgzOVx1Yzc0NCBcdWMyMThcdWQ1ODlcdWQ1NThcdWIyOTRcdWIzNzAgXHVjMGFjXHVjNmE5XHVkNTVjIFx1YWUwMFx1Yzc5MFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIChcdWNkOWNcdWI4MjVcdWQ1NjAgXHVhZTAwXHVjNzkwXHViMDk4IFx1YzBhZFx1YzgxY1x1ZDU2MCBcdWFlMDBcdWM3OTApPFwvcD5cclxuXHJcbjxwPlx1YWMwMFx1YzdhNSBcdWM5ZTdcdWM3NDAgXHVkM2I4XHVjOWQxIFx1YzJhNFx1ZDA2Y1x1YjliZFx1ZDJiOFx1YWMwMCBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWM1NDRcdWJiMzRcdWFjNzBcdWIwOTggXHVjZDljXHViODI1XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxNzE2MSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkVkaXQgZGlzdGFuY2UiLCJkZXNjcmlwdGlvbiI6IjxwPkdpdmVuIGEgc3RyaW5nLCBhbiBlZGl0IHNjcmlwdCBpcyBhIHNldCBvZiBpbnN0cnVjdGlvbnMgdG8gdHVybiBpdCBpbnRvIGFub3RoZXIgc3RyaW5nLiBUaGVyZSBhcmUgZm91ciBraW5kcyBvZiBpbnN0cnVjdGlvbnMgaW4gYW4gZWRpdCBzY3JpcHQ6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+QWRkICgmbHNxdW87YSZyc3F1bzspOiBPdXRwdXQgb25lIGNoYXJhY3Rlci4gVGhpcyBpbnN0cnVjdGlvbiBkb2VzIG5vdCBjb25zdW1lIGFueSBjaGFyYWN0ZXJzIGZyb20gdGhlIHNvdXJjZSBzdHJpbmcuPFwvbGk+XHJcblx0PGxpPkRlbGV0ZSAoJmxzcXVvO2QmcnNxdW87KTogRGVsZXRlIG9uZSBjaGFyYWN0ZXIuIFRoYXQgaXMsIGNvbnN1bWUgb25lIGNoYXJhY3RlciBmcm9tIHRoZSBzb3VyY2Ugc3RyaW5nIGFuZCBvdXRwdXQgbm90aGluZy48XC9saT5cclxuXHQ8bGk+TW9kaWZ5ICgmbHNxdW87bSZyc3F1bzspOiBNb2RpZnkgb25lIGNoYXJhY3Rlci4gVGhhdCBpcywgY29uc3VtZSBvbmUgY2hhcmFjdGVyIGZyb20gdGhlIHNvdXJjZSBzdHJpbmcgYW5kIG91dHB1dCBhIGRpXHVmYjAwZXJlbnQgY2hhcmFjdGVyLjxcL2xpPlxyXG5cdDxsaT5Db3B5ICgmbHNxdW87YyZyc3F1bzspOiBDb3B5IG9uZSBjaGFyYWN0ZXIuIFRoYXQgaXMsIGNvbnN1bWUgb25lIGNoYXJhY3RlciBmcm9tIHRoZSBzb3VyY2Ugc3RyaW5nIGFuZCBvdXRwdXQgdGhlIHNhbWUgY2hhcmFjdGVyLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPldoZW4gd2UgZGlzY3VzcyBkZWxldGluZywgbW9kaWZ5aW5nLCBvciBjb3B5aW5nLCB0aGUgY2hhcmFjdGVyIHRoYXQgbXVzdCBiZSBjb25zdW1lZCBpcyB0aGUgbGVmdG1vc3QgY2hhcmFjdGVyIGluIHRoZSBzdHJpbmcuPFwvcD5cclxuXHJcbjxwPkEgc2hvcnRlc3QgZWRpdCBzY3JpcHQgaXMgYW4gZWRpdCBzY3JpcHQgdGhhdCBtaW5pbWl6ZXMgdGhlIHRvdGFsIG51bWJlciBvZiBhZGRzLCBkZWxldGVzLCBhbmQgbW9kaVx1ZmIwMWVzLjxcL3A+XHJcblxyXG48cD5HaXZlbiB0d28gc3RyaW5ncywgZ2VuZXJhdGUgYSBzaG9ydGVzdCBlZGl0IHNjcmlwdCB0aGF0IGNoYW5nZXMgdGhlIFx1ZmIwMXJzdCBpbnRvIHRoZSBzZWNvbmQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2YgdHdvIHN0cmluZ3Mgb24gc2VwYXJhdGUgbGluZXMuIFRoZSBzdHJpbmdzIGNvbnRhaW4gb25seSBhbHBoYW51bWVyaWMgY2hhcmFjdGVycy4gRWFjaCBzdHJpbmcgaGFzIGxlbmd0aCBiZXR3ZWVuIDEgYW5kIDE3MDAwLCBpbmNsdXNpdmUuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG91dHB1dCBpcyBhIHNob3J0ZXN0IGVkaXQgc2NyaXB0LiBFYWNoIGxpbmUgaXMgb25lIGluc3RydWN0aW9uLCBnaXZlbiBieSB0aGUgb25lLWxldHRlciBjb2RlIG9mIHRoZSBpbnN0cnVjdGlvbiAoYSwgZCwgbSwgb3IgYyksIGZvbGxvd2VkIGJ5IGEgc3BhY2UsIGZvbGxvd2VkIGJ5IHRoZSBjaGFyYWN0ZXIgd3JpdHRlbiAob3IgZGVsZXRlZCBpZiB0aGUgaW5zdHJ1Y3Rpb24gaXMgYSBkZWxldGlvbikuPFwvcD5cclxuXHJcbjxwPkluIGNhc2Ugb2YgYSB0aWUsIHlvdSBtYXkgZ2VuZXJhdGUgYW55IHNob3J0ZXN0IGVkaXQgc2NyaXB0PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

채점 및 기타 정보

  • 예제는 채점하지 않는다.