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

526 - String Distance and Transform Process.cpp

#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;
        lp(k, numAdd) {
            cout << ++indx << " Insert " << i+k+1+indxShift << "," << s2[j+k] << endl;
        }
        indxShift+=numAdd;
        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;
}