1878String Distance and Transform Process

题目描述

String Distance is a non-negative integer that measures the distance between two strings. Here we give the definition. A transform list is a list of string, where each string, except for the last one, can be changed to the string followed by adding a character, deleting a character or replacing a character. The length of a transform list is the count of strings minus 1 (that is the count of operations to transform these two strings). The distance between two strings is the length of a transform list from one string to the other with the minimal length. You are to write a program to calculate the distance between two strings and give the corresponding transform list.

输入格式:

Input consists a sequence of string pairs, each string pair consists two lines, each string occupies one line. The length of each string will be no more than 80.

输出格式:

For each string pair, you should give an integer to indicate the distance between them at the first line, and give a sequence of command to transform string 1 to string 2. Each command is a line lead by command count, then the command. A command must be

Insert pos,value
Delete pos
Replace pos,value

where pos is the position of the string and pos should be between 1 and the current length of the string (in Insert command, pos can be 1 greater than the length), and value is a character. Actually many command lists can satisfy the request, but only one of them is required.

输入样例复制

abcac
bcd
aaa
aabaaaa

输出样例 复制

3
1 Replace 5,d
2 Delete 4
3 Delete 1
4
1 Insert 1,a
2 Insert 1,b
3 Insert 1,a
4 Insert 1,a