Levenshtein

/* Dawid Mocek */

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

#define COST_NOT 0.0
#define COST_ADD 1.0
#define COST_DEL 1.0
#define COST_CHG 1.5


struct FromTo {
    char *from;
    int from_len;
    char *to;
    int to_len;
    double cost;
};

void free_ft(struct FromTo ****ft, int x, int y) {
    int i, j;
    for (i = 0; i < x; i++) {
        for (j = 0; j < y; j++) {
            free((*ft[i][j])->from);
            free((*ft[i][j])->to);
            (*ft[i][j])->from = NULL;
            (*ft[i][j])->to = NULL;
            free(*ft[i][j]);
            (*ft[i][j]) = NULL;
        }
        free((*ft[i]));
    }
}
double minimum(double x1, double x2, double x3)
{
    if (x1 >= x2)
    if (x2 >= x3)
        return x3;
    else
        return x2;
    else
    if (x3 >= x1)
        return x1;

    return x3;
}

double Levenshtein(char *s, int s_len, char *t, int t_len)
{
    int i, j, m, n, l;
        double cost, res;
    double **d = (double **)calloc(s_len + 1, sizeof(double*));
    for (i = 0; i <= t_len; i++)
        d[i] = (double *)calloc(t_len + 1, sizeof(double));

    m = s_len;
    n = t_len;

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

    for (i = 1; i <= m; i++)
    {
        for (j = 1; j <= n; j++)
        {
            if (s[i - 1] == t[j - 1])
                cost = COST_NOT;
            else
                cost = COST_ADD;

            d[i][j] = minimum(  d[i - 1][j] + 1,       /* remove */
                                d[i][j - 1] + 1,       /* insert */
                                d[i - 1][j - 1] + COST_CHG /* change */
                            );
        }
    }


    res = d[m][n];

    return res;
}

struct FromTo ***generuj(char *src, int src_len, char *dst, int dst_len) {
    if (src == NULL || dst == NULL)
        return NULL;

    int i, j, k, l;
    double leven;
    char *src_tmp = NULL, *dst_tmp = NULL;
    struct FromTo* ft_record = NULL;

    struct FromTo ***ft = (struct FromTo ***)malloc(sizeof(struct FromTo **) * src_len);
    for (i = 0; i < src_len; i++)
        ft[i] = (struct FromTo **)malloc(sizeof(struct FromTo*) * dst_len);

    k = 1;
    j = 0;
    for (i = 0; i < src_len; i++, k++) {
        src_tmp = (char *)malloc(((sizeof(char)) * k) + sizeof(char));
        memset(src_tmp, 0, k + 1);
        memcpy(src_tmp, src, sizeof(char) * k);

        l = 1;
        for (j = 0; j < dst_len; j++, l++) {
            dst_tmp = (char *)malloc(((sizeof(char)) * l) + sizeof(char));
            memset(dst_tmp, 0, l + 1);
            memcpy(dst_tmp, dst, sizeof(char)* l);

            ft_record = (struct FromTo *)malloc(sizeof(struct FromTo));
            ft_record->from = src_tmp;
            ft_record->from_len = strlen(src_tmp);
            ft_record->to = dst_tmp;
            ft_record->to_len = strlen(dst_tmp);
            leven = Levenshtein(src_tmp, ft_record->from_len, ft_record->to, ft_record->to_len);
            ft[i][j] = ft_record;
        }
    }

    return ft;
}


int main(void) {

    char *string = "POLITECH";
    char *str = "OLABOGA";
    struct FromTo ***ft  = generuj(string, strlen(string), str, strlen(str));
    return 0;
}