levenshtein.c

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

int levenshtein_distance(const char *s1, const char *s2)
{
    size_t s1_len = strlen(s1);
    size_t s2_len = strlen(s2);
    size_t rows = s1_len + 1;
    size_t cols = s2_len + 1;
    size_t i, j;

    unsigned result;
    unsigned d1, d2, d3;
    unsigned *dist = malloc(rows * cols * sizeof(unsigned));
    if (!dist) {
        return -1;
    }

    for (i = 0; i < rows; i++) {
        dist[i * cols] = i;
    }


    for (j = 0; j < cols; j++) {
        dist[j] = j;
    }

    for (j = 1; j < cols; j++) {
        for (i = 1; i < rows; i++) {
            if (s1[i - 1] == s2[j - 1]) {
                dist[(i * cols) + j] = dist[((i - 1) * cols) + (j - 1)];
            } else {
                d1 = dist[((i - 1) * cols) + j] + 1;
                d2 = dist[(i * cols) + (j - 1)] + 1;
                d3 = dist[((i - 1) * cols) + (j - 1)] + 1;

                dist[(i * cols) + j] = MIN(d1, MIN(d2, d3));
            }
        }
    }

    result = dist[(cols * rows) - 1];

    free(dist);

    return result;
}