-
Notifications
You must be signed in to change notification settings - Fork 0
/
00526.cpp
50 lines (48 loc) · 1.16 KB
/
00526.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <cstdio>
#include <cstring>
#include <algorithm>
#define INS "Insert"
#define DEL "Delete"
#define REP "Replace"
#define M trace(r-1,c-1)
#define R trace(r-1,c-1),printf("%d %s %d,%c\n",++cnt,REP,r + ins - del,s2[c-1])
#define I trace(r,c-1),printf("%d %s %d,%c\n",++cnt,INS,r + 1 + ins - del,s2[c-1]),ins++
#define D trace(r-1,c),printf("%d %s %d\n",++cnt,DEL,r + ins - del),del++
using namespace std;
int cnt,ins,del,arr[81][81];
char s1[81],s2[81];
void trace(int r,int c)
{
if(!arr[r][c]) return;
int t;
if(r != 0 || c != 0)
{
if(r == 0) I;
else if(c == 0) D;
else
{
t = min(arr[r-1][c],min(arr[r][c-1],arr[r-1][c-1]));
if(t == arr[r][c]) M;
else if(t == arr[r-1][c-1]) R;
else if(t == arr[r-1][c]) D;
else I;
}
}
}
int main()
{
int l1 = -1,l2;
for(int i = 0;i <= 80;i++) arr[i][0] = arr[0][i] = i;
while(gets(s1))
{
if(l1 != -1) printf("\n");
l1 = strlen(s1);
l2 = strlen(gets(s2));
for(int i = 1;i <= l1;i++) for(int j = 1;j <= l2;j++)
arr[i][j] = s1[i-1] == s2[j-1] ? arr[i-1][j-1]:(min(arr[i-1][j-1],min(arr[i-1][j],arr[i][j-1])) + 1);
cnt = ins = del = 0;
printf("%d\n",arr[l1][l2]);
trace(l1,l2);
}
return 0;
}