21781_Editdistance

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.

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

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.

abcde
xabzdey

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