#include <iostream>
#include <string.h>
#include <locale>


using namespace std;

int* countMatrix(char *string, char *target, int leng1, int leng2) {

    int i = leng1 + 1;
    int j = leng2 + 1;
    int *D = new int[i*j];
    *D = 0;
    for (int k = 1; k <= i; k++) {
        *(D + j * k) = k;
    }

    for (int g = 1; g <= j; g++) {
        *(D + g) = g;

        for (int k = 1; k <= i; k++) {
            if (string[k - 1] == target[g - 1]) {
                *(D + k * j + g) = *(D + (k - 1) * j + g - 1);
            }
            else {
                *(D + k * j + g) = *(D + (k - 1) * j + g - 1) + 1;
                if (*(D + k * j + g) > *(D + k * j + g - 1) + 1) {
                    *(D + k * j + g) = *(D + k * j + g - 1) + 1;
                }
                if (*(D + k * j + g) > *(D + (k - 1) * j + g) + 1) {
                    *(D + k * j + g) = *(D + (k - 1) * j + g) + 1;
                }
            }
        }
    }


    return D;
}

int LevenshteinDistance(char *string, char *target, int leng1, int leng2) {

    int* D = countMatrix(string, target, leng1, leng2);

    return  *(D + (leng2+1) * leng1 + leng2);
}

typedef struct _bufer{
    int i,j;
}bufer;

void editPrescription(char *string, char *target, int leng1, int leng2){

    int* D = countMatrix(string, target, leng1, leng2);

    int operation,pred;

    int i = leng1+1;
    int j = leng2+1;

    bufer myBufer;

    myBufer.i = leng1;
    myBufer.j = leng2;

    while((myBufer.i != 0) && (myBufer.j != 0)){

        if(myBufer.i == 0){   // if on the edge
            myBufer.j--;
            cout << "insert: " << target[j-1] << endl;
        }else
            if(myBufer.j == 0){
                myBufer.i--;
                cout << "delete: " << string[i-1] << endl;
            }else
            {
                if(string[myBufer.i-1] == target[myBufer.j-1]){  // if match
                    cout << "no changes" << endl;
                    myBufer.i--;
                    myBufer.j--;

                }else{

                    // 0 - change
                    // 1 - insert
                    // 2 - delete
                    pred = *(D + j*(myBufer.i-1) + myBufer.j-1);
                    operation = 0;

                    if (pred > *(D + j*(myBufer.i) + myBufer.j-1)){
                        operation = 1;
                    }

                    if (pred > *(D + j*(myBufer.i-1) + myBufer.j)){
                        operation = 2;
                    }
                    //
                    switch (operation){
                        case 0:
                            cout << "change " << string[myBufer.i-1] << " to " << target[myBufer.j-1] << endl;
                            myBufer.i--;
                            myBufer.j--;
                            break;
                        case 1:
                            cout << "insert " << target[myBufer.j-1] << endl;
                            myBufer.j--;
                            break;
                        case 2:
                            cout << "delete " << string[myBufer.i-1] << endl;
                            myBufer.i--;
                            break;
                    }

                }
            }

    }


}

int main() {

    //setlocale( LC_ALL,"Russian" );


    char myString[5];
    strcpy(myString, "fuck");
    char myString2[6];
    strcpy(myString2, "lucky");

    cout << LevenshteinDistance(myString,myString2, 5, 6);

    editPrescription(myString, myString2, 4, 5);

    //system("pause");
    return 0;


}