mahmoud-a
8/10/2017 - 7:47 PM

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=467

``````#include <bits/stdc++.h>

#define ll long long
#define sz(v) ((int) ((v).size()))
#define clr(v, d) memset(v, d, sizeof(v))
#define lp(i, n) for(int i = 0; i < (int)(n); ++i)
#define rep(i, v) for(int i = 0; i < sz(v); ++i)

using namespace std;

string s1, s2;
int n1, n2;
const int MAX = 81;
const int OO = (int)1e9;
int cache[MAX][MAX];

int minSwitch(int i, int j) {

if(i == n1)
return n2 - j;
if(j == n2)
return n1 - i;

int &ret = cache[i][j];

if(ret != -1)
return ret;

ret = OO;

if(s1[i] == s2[j]) {
return ret = minSwitch(i+1, j+1);
} else {
ret = min(ret, minSwitch(i+1, j+1) + 1); // Replace
ret = min(ret, minSwitch(i+1, j) + 1); // Delete
ret = min(ret, minSwitch(i, j+1) + 1); // Insert
}

return ret;
}

int indx = 0;
int indxShift;
void traceOperations(int i, int j) {
if(i == n1) {
int numAdd = n2 - j;
cout << ++indx << " Insert " << i+k+1+indxShift << "," << s2[j+k] << endl;
}
return ;
}

if(j == n2) {
int numDel = n1 - i;
lp(k, numDel) {
cout << ++indx << " Delete " << i+k+1+indxShift << endl;
--indxShift;
}
return;
}

if(s1[i] == s2[j]) {
return traceOperations(i+1, j+1);
}

int c1 = minSwitch(i+1, j+1) + 1; // Replace
int c2 = minSwitch(i+1, j) + 1; // Delete
int c3 = minSwitch(i, j+1) + 1; // Insert

int opt = minSwitch(i, j);
if(opt == c1) { // Replace
cout << ++indx << " Replace " << i+1+indxShift << "," <<s2[j] << endl;
traceOperations(i+1, j+1);
} else if(opt == c2) { // Delete
cout << ++indx << " Delete " << i+1+indxShift << endl;
--indxShift;
traceOperations(i+1, j);
} else { // Insert
cout << ++indx << " Insert " << i+1+indxShift << "," << s2[j] << endl;
++indxShift;
traceOperations(i, j+1);
}
}

int main() {
while(getline(cin, s1) && getline(cin, s2)) {
clr(cache, -1);
n1 = s1.length();
n2 = s2.length();
cout << minSwitch(0, 0) << endl;

indxShift = indx = 0;
traceOperations(0, 0);
}
return 0;
}
``````