#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <string.h>

#define MAXNCHARS 16

int Levenshtein_distance(char *x, char *y);
int Levenshtein_distance_v2(char *x, char *y);
int minimum(int a, int b, int c);

int main(void) {
    printf("Inserisci v1/v2: ");
    char choice[2];

    scanf ("%[^\n]%*c", choice);
    char str1[MAXNCHARS], str2[MAXNCHARS];
    printf("Inserisci due stringhe:\n");
    scanf ("%[^\n]%*c", str1);
    scanf ("%[^\n]%*c", str2);
    int d;
    if (strcmp(choice,"v1")) {
        d = Levenshtein_distance(str1,str2);
    } else if (strcmp(choice,"v2")) {
        d = Levenshtein_distance_v2(str1,str2);
    }

    printf("La distanza di Levenshtein e': %d", d);
    return 0;
}

int Levenshtein_distance(char *x, char *y) {
    int m = strlen(x);
    int n = strlen(y);

    int i, j;

    int distance;

    int **d = (int**) malloc((m + 1) * sizeof(int*));

    for(i = 0; i <= m; i++)
        d[i] = (int*) malloc((n + 1) * sizeof(int));

    for(i = 0; i <= m; i++)
        d[i][0] = i;

    for(j = 1; j <= n; j++)
        d[0][j] = j;

    for(i = 1; i <= m; i++) {
        for(j = 1; j <= n; j++) {
            if(x[i - 1] != y[j - 1]) {
                int k = minimum(
                    d[i][j - 1],
                    d[i - 1][j],
                    d[i - 1][j - 1]
                );
                d[i][j] = k + 1;
            } else {
                d[i][j] = d[i - 1][j - 1];
            }
        }
    }

    distance = d[m][n];

    for(i = 0; i <= m; i++)
        free(d[i]);

    free(d);
    return distance;
}


int Levenshtein_distance_v2(char *x, char *y) {
    int m = strlen(x);
    int n = strlen(y);
    int i, j;
    int distance;
    int *prev = (int*) malloc((n + 1) * sizeof(int));
    int *curr = (int*) malloc((n + 1) * sizeof(int));
    int *tmp = 0;
    for(i = 0; i <= n; i++)
        prev[i] = i;
    for(i = 1; i <= m; i++) {
        curr[0] = i;
        for(j = 1; j <= n; j++) {
            if(x[i - 1] != y[j - 1]) {
                int k = minimum(curr[j - 1], prev[j - 1], prev[j]);
                curr[j] = k + 1;
                } else {
                    curr[j] = prev[j - 1];
            }
        }
        tmp = prev;
        prev = curr;
        curr = tmp;
        memset((void*) curr, 0, sizeof(int) * (n + 1));
    }
    distance = prev[n];
    free(curr);
    free(prev);
    return distance;
}

int minimum(int a, int b, int c) {

/* funzione che calcola il minimo di 3 valori */

    int min = a;

    if (b < min) min = b;
    if (c < min) min = c;

    return min;
}