#### 48 lines 1.0 KiB C Raw Permalink Blame History

 ```#include ``` ```#include ``` ```#include ``` ``` ``` ```/*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; ``` ```} ```