48 lines
1.0 KiB
C
48 lines
1.0 KiB
C
#include <stdlib.h>
|
|
#include <malloc.h>
|
|
#include <string.h>
|
|
|
|
/*Compute levenshtein distance between s and t*/
|
|
int levenshtein_distance(char *s, char*t) {
|
|
//Step 1
|
|
int i, j, k, n, m, cost, *d, distance;
|
|
n = strlen(s);
|
|
m = strlen(t);
|
|
if (n != 0 && m != 0) {
|
|
d = malloc((sizeof(int)) * (m + 1) * (n + 1));
|
|
m++;
|
|
n++;
|
|
//Step 2
|
|
for (k = 0; k < n; k++)
|
|
d[k] = k;
|
|
for (k = 0; k < m; k++)
|
|
d[k*n] = k;
|
|
//Step 3 and 4
|
|
for (i = 1; i < n; i++)
|
|
for (j = 1; j < m; j++) {
|
|
//Step 5
|
|
if (s[i-1] == t[j-1])
|
|
cost = 0;
|
|
else
|
|
cost = 1;
|
|
//Step 6
|
|
d[j*n+i] = minimum(d[(j-1)*n + i] + 1, d[j*n+i-1] + 1, d[(j-1)*n + i - 1] + cost);
|
|
}
|
|
distance = d[n*m-1];
|
|
free(d);
|
|
return distance;
|
|
}
|
|
else
|
|
return -1; //a negative return value means that one or both strings are empty.
|
|
}
|
|
|
|
/*Gets the minimum of three values*/
|
|
int minimum(int a, int b, int c) {
|
|
int min = a;
|
|
if (b < min)
|
|
min = b;
|
|
if (c < min)
|
|
min = c;
|
|
return min;
|
|
}
|