edit distance implementation based on http://nlp.stanford.edu/IR-book/html/htmledition/edit-distance-1.html

distance.c

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

static int
min(int i, int j, int k)
{
	int min = i;
	if (min > j)
		min = j;
	if (min > k)
		min = k;
	return min;
}

static int
edit_distance(char *s1, char *s2)
{
	size_t i, j;
	size_t len1 = strlen(s1);
	size_t len2 = strlen(s2);
	int m[len1][len2];
	for (i = 0; i < len1; i++)
		for(j = 0; j < len2; j++)
			m[i][j] = 0;

	for (i = 1; i < len1; i++)
		m[i][0] = i;
	for (i = 1; i < len2; i++)
		m[0][i] = i;

	for (i = 1; i < len1; i++)
		for (j = 1; j < len2; j++)
			m[i][j] = min(m[i - 1][j - 1] + s1[i] == s2[j]? 0: 2,
					m[i - 1][j] + 1,
					m[i][j - 1] + 1);
	return m[len1 - 1][len2 - 1];
}

int main(int argc, char **argv)
{
	if (argc < 3) {
		fprintf(stderr, "Usage: distance <string1> <string2>");
		return -1;
	}

	char *s1 = argv[1];
	char *s2 = argv[2];
	int distance = edit_distance(s1, s2);
	printf("%d\n", distance);
	return 0;
}