편집 거리 (Hard)
시간 제한8초메모리 제한16 MB
첫 번째 문자열을 두 번째 문자열로 바꾸는 최소 명령 수열(삽입, 삭제, 변경, 복사)을 구합니다. 각 문자열은 최대 17000자입니다.
문제
문자열 하나가 주어졌을 때, 이 문자열을 다른 문자열로 바꾸는 편집 스크립트를 작성하려고 한다. 편집 스크립트에서 사용할 수 있는 명령은 다음 네 가지이다.
- 추가 ('a'): 한 글자를 출력한다. 이 명령은 입력 문자열을 건드리지 않는다.
- 삭제 ('d'): 입력 문자열의 맨 앞 글자를 삭제한다. 아무것도 출력하지 않는다.
- 수정 ('m'): 입력 문자열의 맨 앞 글자를 삭제하고, 바꾼 글자를 출력한다.
- 복사 ('c'): 입력 문자열의 맨 앞 글자를 삭제하고, 삭제한 그 글자를 출력한다.
가장 짧은 편집 스크립트는 추가, 삭제, 수정을 가장 적게 사용한 스크립트이다.
두 문자열이 주어졌을 때, 첫 번째 문자열을 두 번째 문자열로 바꾸는 가장 짧은 편집 스크립트를 작성하는 프로그램을 작성하시오.
입력
두 문자열이 한 줄에 하나씩 주어진다. 각 문자열은 영문 알파벳과 숫자로만 이루어져 있으며, 길이는 1 이상 17000 이하이다.
출력
가장 짧은 편집 스크립트를 출력한다. 명령은 한 줄에 하나씩 출력하며, 각 줄에는 명령 문자 (a, d, m, c) 중 하나와 그 명령에 사용한 글자를 출력한다. 글자는 출력할 글자나 삭제할 글자이다.
가장 짧은 편집 스크립트가 여러 가지인 경우에는 아무거나 출력하면 된다.