시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
8 초 128 MB 825 164 53 12.269%

문제

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

  • 추가 ('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
W3sicHJvYmxlbV9pZCI6Ijc2MjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzYjhcdWM5ZDEgXHVhYzcwXHViOWFjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzc0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWIyZTRcdWI5NzggXHViYjM4XHVjNzkwXHVjNWY0XHViODVjIFx1YmMxNFx1YWZiOFx1YjI5NCBcdWQzYjhcdWM5ZDEgXHVjMmE0XHVkMDZjXHViOWJkXHVkMmI4XHViOTdjIFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1ZDNiOFx1YzlkMSBcdWMyYTRcdWQwNmNcdWI5YmRcdWQyYjhcdWM1ZDBcdWMxMWMgXHVjMGFjXHVjNmE5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYTg1XHViODM5XHVjNzQwIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NzQgXHVjZDFkIFx1YjEyNCBcdWFjMDBcdWM5YzBcdWFjMDAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1Y2Q5NFx1YWMwMCAoJiMzOTthJiMzOTspOiBcdWQ1NWMgXHVhZTAwXHVjNzkwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YmE4NVx1YjgzOVx1Yzc0MCBcdWM3ODVcdWI4MjUgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1YWM3NFx1YjRkY1x1YjlhY1x1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzBhZFx1YzgxYyAoJiMzOTtkJiMzOTspOiBcdWQ1NWMgXHVhZTAwXHVjNzkwXHViOTdjIFx1YzBhZFx1YzgxY1x1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YmE4NVx1YjgzOVx1Yzc0MCBcdWM3ODVcdWI4MjUgXHViYjM4XHVjNzkwXHVjNWY0XHVjNWQwXHVjMTFjIFx1YjllOCBcdWM1NWUgXHVhZTAwXHVjNzkwXHViOTdjIFx1YzBhZFx1YzgxY1x1ZDU1OFx1YWNlMCwgXHVjNTQ0XHViYjM0XHVhYzgzXHViM2M0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzIxOFx1YzgxNSAoJiMzOTttJiMzOTspOiBcdWQ1NWMgXHVhZTAwXHVjNzkwXHViOTdjIFx1YzIxOFx1YzgxNVx1ZDU1Y1x1YjJlNC4gXHVjOTg5LCBcdWM3ODVcdWI4MjUgXHViYjM4XHVjNzkwXHVjNWY0XHVjNWQwXHVjMTFjIFx1YjllOCBcdWM1NWUgXHVhZTAwXHVjNzkwXHViOTdjIFx1YzBhZFx1YzgxY1x1ZDU1OFx1YWNlMCwgXHViYzE0XHVhZmJjIFx1YWUwMFx1Yzc5MFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YmNmNVx1YzBhYyAoJiMzOTtjJiMzOTspOiBcdWQ1NWMgXHVhZTAwXHVjNzkwXHViOTdjIFx1YmNmNVx1YzBhY1x1ZDU1Y1x1YjJlNC4gXHVjNzg1XHViODI1XHVjNWQwXHVjMTFjIFx1YjllOCBcdWM1NWUgXHVhZTAwXHVjNzkwXHViOTdjIFx1YzBhZFx1YzgxY1x1ZDU1OFx1YWNlMCwgXHVjMGFkXHVjODFjXHVkNTVjIFx1YWRmOCBcdWFlMDBcdWM3OTBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YWMwMFx1YzdhNSBcdWM5ZTdcdWM3NDAgXHVkM2I4XHVjOWQxIFx1YzJhNFx1ZDA2Y1x1YjliZFx1ZDJiOFx1Yjc4MCwgXHVjZDk0XHVhYzAwLCBcdWMwYWRcdWM4MWMsIFx1YzIxOFx1YzgxNVx1Yzc0NCBcdWFjMDBcdWM3YTUgXHVjODAxXHVhYzhjIFx1YzBhY1x1YzZhOVx1ZDU1YyBcdWMyYTRcdWQwNmNcdWI5YmRcdWQyYjhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWI4NWMgXHViYzE0XHVhZmI4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWM5ZTdcdWM3NDAgXHVkM2I4XHVjOWQxIFx1YzJhNFx1ZDA2Y1x1YjliZFx1ZDJiOFx1Yjk3YyBcdWM3OTFcdWMxMzFcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1YjQ1MCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwIFx1YzYwMVx1YmIzOFx1YzU0Y1x1ZDMwY1x1YmNiM1x1YWNmYyBcdWMyMmJcdWM3OTBcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVhZTM4XHVjNzc0XHViMjk0IDFcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgMTcwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDBcdWM3YTUgXHVjOWU3XHVjNzQwIFx1ZDNiOFx1YzlkMSBcdWMyYTRcdWQwNmNcdWI5YmRcdWQyYjhcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWQ1NWMgXHViYTg1XHViODM5XHVjNzQ0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3MCwgXHViYjM4XHVjODFjXHVjNzU4IFx1YWQwNFx1ZDYzOFx1YzVkMCBcdWIwOThcdWM2NDBcdWM3ODhcdWIyOTQgKGEsIGQsIG0sIGMpXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWFjZTAsIFx1YWRmOCBcdWJhODVcdWI4MzlcdWM3NDQgXHVjMjE4XHVkNTg5XHVkNTU4XHViMjk0XHViMzcwIFx1YzBhY1x1YzZhOVx1ZDU1YyBcdWFlMDBcdWM3OTBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiAoXHVjZDljXHViODI1XHVkNTYwIFx1YWUwMFx1Yzc5MFx1YjA5OCBcdWMwYWRcdWM4MWNcdWQ1NjAgXHVhZTAwXHVjNzkwKTxcL3A+XHJcblxyXG48cD5cdWFjMDBcdWM3YTUgXHVjOWU3XHVjNzQwIFx1ZDNiOFx1YzlkMSBcdWMyYTRcdWQwNmNcdWI5YmRcdWQyYjhcdWFjMDAgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjNTQ0XHViYjM0XHVhYzcwXHViMDk4IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNzYyMCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkVkaXQgZGlzdGFuY2UiLCJkZXNjcmlwdGlvbiI6IjxwPkdpdmVuIGEgc3RyaW5nLCBhbiBlZGl0IHNjcmlwdCBpcyBhIHNldCBvZiBpbnN0cnVjdGlvbnMgdG8gdHVybiBpdCBpbnRvIGFub3RoZXIgc3RyaW5nLiBUaGVyZSBhcmUgZm91ciBraW5kcyBvZiBpbnN0cnVjdGlvbnMgaW4gYW4gZWRpdCBzY3JpcHQ6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+QWRkICgmbHNxdW87YSZyc3F1bzspOiBPdXRwdXQgb25lIGNoYXJhY3Rlci4gVGhpcyBpbnN0cnVjdGlvbiBkb2VzIG5vdCBjb25zdW1lIGFueSBjaGFyYWN0ZXJzIGZyb20gdGhlIHNvdXJjZSBzdHJpbmcuPFwvbGk+XHJcblx0PGxpPkRlbGV0ZSAoJmxzcXVvO2QmcnNxdW87KTogRGVsZXRlIG9uZSBjaGFyYWN0ZXIuIFRoYXQgaXMsIGNvbnN1bWUgb25lIGNoYXJhY3RlciBmcm9tIHRoZSBzb3VyY2Ugc3RyaW5nIGFuZCBvdXRwdXQgbm90aGluZy48XC9saT5cclxuXHQ8bGk+TW9kaWZ5ICgmbHNxdW87bSZyc3F1bzspOiBNb2RpZnkgb25lIGNoYXJhY3Rlci4gVGhhdCBpcywgY29uc3VtZSBvbmUgY2hhcmFjdGVyIGZyb20gdGhlIHNvdXJjZSBzdHJpbmcgYW5kIG91dHB1dCBhIGRpXHVmYjAwZXJlbnQgY2hhcmFjdGVyLjxcL2xpPlxyXG5cdDxsaT5Db3B5ICgmbHNxdW87YyZyc3F1bzspOiBDb3B5IG9uZSBjaGFyYWN0ZXIuIFRoYXQgaXMsIGNvbnN1bWUgb25lIGNoYXJhY3RlciBmcm9tIHRoZSBzb3VyY2Ugc3RyaW5nIGFuZCBvdXRwdXQgdGhlIHNhbWUgY2hhcmFjdGVyLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPldoZW4gd2UgZGlzY3VzcyBkZWxldGluZywgbW9kaWZ5aW5nLCBvciBjb3B5aW5nLCB0aGUgY2hhcmFjdGVyIHRoYXQgbXVzdCBiZSBjb25zdW1lZCBpcyB0aGUgbGVmdG1vc3QgY2hhcmFjdGVyIGluIHRoZSBzdHJpbmcuPFwvcD5cclxuXHJcbjxwPkEgc2hvcnRlc3QgZWRpdCBzY3JpcHQgaXMgYW4gZWRpdCBzY3JpcHQgdGhhdCBtaW5pbWl6ZXMgdGhlIHRvdGFsIG51bWJlciBvZiBhZGRzLCBkZWxldGVzLCBhbmQgbW9kaVx1ZmIwMWVzLjxcL3A+XHJcblxyXG48cD5HaXZlbiB0d28gc3RyaW5ncywgZ2VuZXJhdGUgYSBzaG9ydGVzdCBlZGl0IHNjcmlwdCB0aGF0IGNoYW5nZXMgdGhlIFx1ZmIwMXJzdCBpbnRvIHRoZSBzZWNvbmQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2YgdHdvIHN0cmluZ3Mgb24gc2VwYXJhdGUgbGluZXMuIFRoZSBzdHJpbmdzIGNvbnRhaW4gb25seSBhbHBoYW51bWVyaWMgY2hhcmFjdGVycy4gRWFjaCBzdHJpbmcgaGFzIGxlbmd0aCBiZXR3ZWVuIDEgYW5kIDE3MDAwLCBpbmNsdXNpdmUuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG91dHB1dCBpcyBhIHNob3J0ZXN0IGVkaXQgc2NyaXB0LiBFYWNoIGxpbmUgaXMgb25lIGluc3RydWN0aW9uLCBnaXZlbiBieSB0aGUgb25lLWxldHRlciBjb2RlIG9mIHRoZSBpbnN0cnVjdGlvbiAoYSwgZCwgbSwgb3IgYyksIGZvbGxvd2VkIGJ5IGEgc3BhY2UsIGZvbGxvd2VkIGJ5IHRoZSBjaGFyYWN0ZXIgd3JpdHRlbiAob3IgZGVsZXRlZCBpZiB0aGUgaW5zdHJ1Y3Rpb24gaXMgYSBkZWxldGlvbikuPFwvcD5cclxuXHJcbjxwPkluIGNhc2Ugb2YgYSB0aWUsIHlvdSBtYXkgZ2VuZXJhdGUgYW55IHNob3J0ZXN0IGVkaXQgc2NyaXB0PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

University > The MIT Programming Contest > 2008-09 > MIT Programming Contest Team Contest 1 2008 1번