시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcblxyXG48cD5cdWFjMDBcdWM3YTUgXHVjOWU3XHVjNzQwIFx1ZDNiOFx1YzlkMSBcdWMyYTRcdWQwNmNcdWI5YmRcdWQyYjhcdWFjMDAgXHVjNWVjXHViN2VjXHVhYzAwXHVjOWMwXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWM1NDRcdWJiMzRcdWFjNzBcdWIwOTggXHVjZDljXHViODI1XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI3NjIwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRWRpdCBkaXN0YW5jZSIsImRlc2NyaXB0aW9uIjoiPHA+R2l2ZW4gYSBzdHJpbmcsIGFuIGVkaXQgc2NyaXB0IGlzIGEgc2V0IG9mIGluc3RydWN0aW9ucyB0byB0dXJuIGl0IGludG8gYW5vdGhlciBzdHJpbmcuIFRoZXJlIGFyZSBmb3VyIGtpbmRzIG9mIGluc3RydWN0aW9ucyBpbiBhbiBlZGl0IHNjcmlwdDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5BZGQgKCZsc3F1bzthJnJzcXVvOyk6IE91dHB1dCBvbmUgY2hhcmFjdGVyLiBUaGlzIGluc3RydWN0aW9uIGRvZXMgbm90IGNvbnN1bWUgYW55IGNoYXJhY3RlcnMgZnJvbSB0aGUgc291cmNlIHN0cmluZy48XC9saT5cclxuXHQ8bGk+RGVsZXRlICgmbHNxdW87ZCZyc3F1bzspOiBEZWxldGUgb25lIGNoYXJhY3Rlci4gVGhhdCBpcywgY29uc3VtZSBvbmUgY2hhcmFjdGVyIGZyb20gdGhlIHNvdXJjZSBzdHJpbmcgYW5kIG91dHB1dCBub3RoaW5nLjxcL2xpPlxyXG5cdDxsaT5Nb2RpZnkgKCZsc3F1bzttJnJzcXVvOyk6IE1vZGlmeSBvbmUgY2hhcmFjdGVyLiBUaGF0IGlzLCBjb25zdW1lIG9uZSBjaGFyYWN0ZXIgZnJvbSB0aGUgc291cmNlIHN0cmluZyBhbmQgb3V0cHV0IGEgZGlcdWZiMDBlcmVudCBjaGFyYWN0ZXIuPFwvbGk+XHJcblx0PGxpPkNvcHkgKCZsc3F1bztjJnJzcXVvOyk6IENvcHkgb25lIGNoYXJhY3Rlci4gVGhhdCBpcywgY29uc3VtZSBvbmUgY2hhcmFjdGVyIGZyb20gdGhlIHNvdXJjZSBzdHJpbmcgYW5kIG91dHB1dCB0aGUgc2FtZSBjaGFyYWN0ZXIuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+V2hlbiB3ZSBkaXNjdXNzIGRlbGV0aW5nLCBtb2RpZnlpbmcsIG9yIGNvcHlpbmcsIHRoZSBjaGFyYWN0ZXIgdGhhdCBtdXN0IGJlIGNvbnN1bWVkIGlzIHRoZSBsZWZ0bW9zdCBjaGFyYWN0ZXIgaW4gdGhlIHN0cmluZy48XC9wPlxyXG5cclxuPHA+QSBzaG9ydGVzdCBlZGl0IHNjcmlwdCBpcyBhbiBlZGl0IHNjcmlwdCB0aGF0IG1pbmltaXplcyB0aGUgdG90YWwgbnVtYmVyIG9mIGFkZHMsIGRlbGV0ZXMsIGFuZCBtb2RpXHVmYjAxZXMuPFwvcD5cclxuXHJcbjxwPkdpdmVuIHR3byBzdHJpbmdzLCBnZW5lcmF0ZSBhIHNob3J0ZXN0IGVkaXQgc2NyaXB0IHRoYXQgY2hhbmdlcyB0aGUgXHVmYjAxcnN0IGludG8gdGhlIHNlY29uZC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiB0d28gc3RyaW5ncyBvbiBzZXBhcmF0ZSBsaW5lcy4gVGhlIHN0cmluZ3MgY29udGFpbiBvbmx5IGFscGhhbnVtZXJpYyBjaGFyYWN0ZXJzLiBFYWNoIHN0cmluZyBoYXMgbGVuZ3RoIGJldHdlZW4gMSBhbmQgMTcwMDAsIGluY2x1c2l2ZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IGlzIGEgc2hvcnRlc3QgZWRpdCBzY3JpcHQuIEVhY2ggbGluZSBpcyBvbmUgaW5zdHJ1Y3Rpb24sIGdpdmVuIGJ5IHRoZSBvbmUtbGV0dGVyIGNvZGUgb2YgdGhlIGluc3RydWN0aW9uIChhLCBkLCBtLCBvciBjKSwgZm9sbG93ZWQgYnkgYSBzcGFjZSwgZm9sbG93ZWQgYnkgdGhlIGNoYXJhY3RlciB3cml0dGVuIChvciBkZWxldGVkIGlmIHRoZSBpbnN0cnVjdGlvbiBpcyBhIGRlbGV0aW9uKS48XC9wPlxyXG5cclxuPHA+SW4gY2FzZSBvZiBhIHRpZSwgeW91IG1heSBnZW5lcmF0ZSBhbnkgc2hvcnRlc3QgZWRpdCBzY3JpcHQ8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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