1 #include <string>
2 #include <iostream>
3 using namespace std;
4 int b[51][51];//存储最小编辑距离
5 int op[51][51];//存储转换操作
6 int min(int x,int y,int z)
7 {
8 int temp;
9 if(x<y)
10 {
11 temp=x;
12 }
13 else temp=y;
14 if(z<temp) temp=z;
15 return temp;
16 }
17 int opc(int x,int y,int z)
18 {
19 if(x<=y&&x<=z)return 1;
20 if(y<=x&&y<=z)return 2;
21 return 3;
22 }
23 int editDistance(string s,string aim)
24 {
25 int sLength=s.length();
26 int aLength=aim.length();
27
28 for(int i=1;i<=sLength;i++)
29 {
30 b[0][i]=i;
31 op[0][i]=2;
32 }
33 for(int k=1;k<=aLength;k++)
34 {
35 b[k][0]=k;
36 op[k][0]=1;
37 }
38 for(int j=1;j<=sLength;j++)
39 {
40 for(int i=1;i<=aLength;i++)
41 {
42 int x=b[i-1][j]+1;
43 int y=b[i][j-1]+1;
44 int z=b[i-1][j-1]+(s[j-1]==aim[i-1]?0:1);
45 b[i][j]=min(x,y,z);
46 op[i][j]=opc(x,y,z);
47 }
48 }
49 return b[aLength][sLength];
50 }
51 void printRes(string s,string aim)
52 {
53 int j=s.length();
54 int i=aim.length();
55 cout<<s<<endl;
56 while(j!=0||i!=0)
57 {
58 int x=op[i][j];
59 if(3==x)
60 {
61 if(s[j-1]!=aim[i-1])
62 {
63 s[j-1]=aim[i-1];
64 cout<<s<<endl;
65 }
66 i--,j--;
67 continue;
68 }
69 if(2==x)
70 {
71 s.erase(j-1,1);
72 j--;
73 }
74 else
75 if(1==x)
76 {
77 s.insert(s.begin()+j,1,aim[i-1]);
78 i--;
79 }
80 cout<<s<<endl;
81 }
82 }
83 int main()
84 {
85 string s;
86 string aim;
87 cin>>s>>aim;
88 int edit=editDistance(s,aim);
89 printRes(s,aim);
90 //cout<<edit<<endl;
91 return 0;
92 }
93