String 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 strings, 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.
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 Delete 1 2 Replace 3,d 3 Delete 4 4 1 Insert 1,a 2 Insert 2,a 3 Insert 3,b 4 Insert 7,a