Edit distance

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

2009 Multi-University Training Contest 10 - Host by NIT