Given a string, an edit script is a set of instructions to turn it into another string. There are 
four kinds of instructions in an edit script: 
Add (‘a’): Output one character. This instruction does not consume any characters 
from the source string. 
Delete (‘d’): Delete one character. That is, consume one character from the source string and output nothing. 
Modify (‘m’): Modify one character. That is, consume one character from the source string and output a character. 
Copy (‘c’): Copy one character. That is, consume one character from the source string and output the same character. 
Now, We define that A shortest edit script is an edit script that minimizes the total number of adds and deletes. 
Given two strings, generate a shortest edit script that changes the first into the second. 

 

Input

The input consists of two strings on separate lines. The strings contain only alphanumeric 
characters. Each string has length between 1 and 10000, inclusive. 

Output

The output is a shortest edit script. Each line is one instruction, given by the one-letter code of the instruction (a, d, m, or c), followed by a space, followed by the character written (or deleted if the instruction is a deletion). 

In case of a tie, you must generate shortest edit script, and must sort in order of a , d, m, c. 
Therefore, there is only one answer. 

Sample Input

abcde
xabzdey

Sample Output

a x
a a
m b
m z
m d
m e
m y

题意：一开始有一个串1

让你通过四种操作（从前往后）产生串2

1.a #直接在串2添加字符#

2.d #删除串1的字符#

3.m #将串1的字符转化为#放到串2中

4.c #将串1的字符复制粘贴到串2中

要求 ad的个数尽量少 操作数尽量少 

题解：长度不同的直接a 添加或删除d 

剩下的直接转化

#include <bits/stdc++.h>
using namespace std;
int main(){
    string a,b;
    while(cin>>a>>b){
        int an=a.size(),bn=b.size();
        if(an>bn){
            int t=an-bn;
            for(int i=0;i<t;i++)printf("d %c\n",a[i]);
            for(int i=0;i<bn;i++)printf("m %c\n",b[i]);
        }
        else if(an<bn){
            int t=bn-an;
            for(int i=0;i<t;i++)printf("a %c\n",b[i]);
            for(int i=t;i<bn;i++)printf("m %c\n",b[i]);
        }else for(int i=0;i<bn;i++)printf("m %c\n",b[i]);
    }
    return 0;
   // system("pause");
}