Levenshtein distance in plain C

levensthein.c

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


#define MIN(x, y) (((x) < (y)) ? (x) : (y))


typedef struct {
  int *data;
  int w;
  int h;
} iMat;


int at(iMat *m, int i, int j) {
  return m->data[i * m->h + j];
}


void set(iMat *m, int i, int j, int val) {
  m->data[i * m->h + j] = val;
}


void init(iMat *m, int w, int h, int val) {
  m -> w = w;
  m -> h = h;
  m -> data = (int*) malloc(sizeof(int) * w * h);
  for(int i = 0; i < w * h; i++) {
    m -> data[i] = val;
  }
}


int levensthein(char *x, char *y, int n, int m) {
  iMat dp;
  init(&dp, n + 1, m + 1, n * m);
  for(int i = 0; i < n + 1; i++) {
    set(&dp, i, 0, i);
  }
  for(int j = 0; j < n + 1; j++) {
    set(&dp, 0, j, j);
  }
  for(int i = 1; i < n + 1; i++) {
    for(int j = 1; j < m + 1; j++) {
      int match = 0;
      if(x[i - 1] != y[j - 1]) {
	match = 1;
      }
      int align = MIN(at(&dp, i - 1, j) + 1, at(&dp, i, j - 1) + 1);
      int err   = MIN(align, at(&dp, i - 1, j - 1) + match);
      set(&dp, i, j, err);
    }
  }
  return at(&dp, n, m);
}


int main(int argc, char **argv) {
  if (argc == 3) {
      char *x = argv[1];
      char *y = argv[2];
      printf("Levensthein(%s, %s) = %d\n", x, y, levensthein(x,y,strlen(x),strlen(y)));
  } else {
    printf("Usage: ./levensthein strg1 strg2\n");
  }
  return 0;
}