I regret to say that the implementations I psoted before are, though plausible, incorrect, and will fail on some inputs. (The man pages contain one; the Levenshtein and Damerau-Levenshtein distances from 'terrible' to 'tribble' are 3, not 2.) Correct implementations:

`int levenshtein_distance(string a, string b) {`

int alen = strlen(a);

int blen = strlen(b);

mixed array dist = allocate(alen + 1, allocate(blen + 1));

for(int i = 1; i <= alen; i++)

dist[i][0] = i;

int array dist0 = dist[0];

for(int j = 1; j <= blen; j++)

dist0[j] = j;

for(int i = 0; i < alen; i++)

for(int j = 0; j < blen; j++)

dist[i + 1][j + 1] = min(dist[i][j + 1] + 1, dist[i + 1][j] + 1, dist[i][j] + (a[i] != b[j]));

return dist[alen][blen];

}

int damerau_levenshtein_distance(string a, string b) {

int alen = strlen(a);

int blen = strlen(b);

mixed array dist = allocate(alen + 1, allocate(blen + 1));

for(int i = 1; i <= alen; i++)

dist[i][0] = i;

int array dist0 = dist[0];

for(int j = 1; j <= blen; j++)

dist0[j] = j;

for(int i = 0; i < alen; i++)

for(int j = 0; j < blen; j++)

if(i && j && a[i] == b[j - 1] && a[i - 1] == b[j])

dist[i + 1][j + 1] = min(dist[i][j + 1] + 1, dist[i + 1][j] + 1, dist[i][j] + (a[i] != b[j]), dist[i - 1][j - 1] + (a[i] != b[j]));

else

dist[i + 1][j + 1] = min(dist[i][j + 1] + 1, dist[i + 1][j] + 1, dist[i][j] + (a[i] != b[j]));

return dist[alen][blen];

}