We usu­ally want to talk about Lev­en­shtein dis­tance when we want to com­pare two dif­fer­ent strings. Prat­i­cally, the Lev­en­shtein dis­tance (as its creator’s name, Vladimir Lev­en­shtein) is a mea­sure of the sim­i­lar­ity between two strings. If you want to look at the algo­rithm in detail, then you should take a look at this page avail­able on wikipedia.

The Lev­en­shtein dis­tance is noth­ing but else than the number of steps needed to trans­form a string into another one. For exam­ple, if we want to go from “cat” to “cats”, then we have a Lev­en­shtein dis­tance equal to 1 (since we added only a ‘s’, so one step).

Here is the code I done (tested with gcc, after a strip --strip-unneeded is only 4.5kb large):

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

#define MAX_STR_LEN     100

typedef unsigned short int Matrix;

static int levenshtein(const char *, const char *);
static int min(const int, const int, const int);
static char *strlower(char *);

int
main(int argc, char **argv)
{
        unsigned short int i, ss, c_sens = 1;
        char str[1][MAX_STR_LEN];

if (argc < 3) {
                printf("Usage: %s [-i] <string1> <string2>n", argv[0]);
                return EXIT_FAILURE;
        }

ss = 0;
        for (i = 1; i < argc; i++)
        {
                if (!strcmp(argv[i], "-i")) {
                        c_sens = 0;
                } else {
                        strcpy(str[ss], argv[i]);
                        ss++;
                }
        }

if (!c_sens) {
                strlower(str[0]);
                strlower(str[1]);
        }

printf("[%s]/[%s]:%dn", str[0], str[1], levenshtein(str[0], str[1]));

return EXIT_SUCCESS;
}

static int
levenshtein(const char *str1, const char *str2)
{
        unsigned short int n, m, i, j, cost;
        Matrix matrix[MAX_STR_LEN][MAX_STR_LEN];

n = strlen(str1);
        m = strlen(str2);

if (n == 0)
                return m;
        if (m == 0)
                return n;

for (i = 0; i <= n; i++)
                matrix[i][0] = i;
        for (i = 0; i <= m; i++)
                matrix[0][i] = i;

for (i = 1; i <= n; i++)
        {
                for (j = 1; j <= m; j++)
                {
                        cost = ((str1[i - 1] == str2[j - 1]) ? 0 : 1);
                        matrix[i][j] = min(     matrix[i - 1][j] + 1,
                                                matrix[i][j - 1] + 1,
                                                matrix[i - 1][j - 1] + cost);
                }
        }

return matrix[n][m];
}

static int
min(const int a, const int b, const int c)
{
        unsigned short int min = a;

if (b < min)
                min = b;

if (c < min)
                min = c;

return min;
}

static char *
strlower(char *a)
{
        unsigned short int i, len = strlen(a);

for (i = 0; i < len; i++)
                *(a + i) = tolower(*(a + i));

return a;
}

If you want a case insen­si­tive com­pu­ta­tion, use the -i switch on the com­mand line.
This ver­sion could be improved by using point­ers when threat­ing the matrix, but maybe I would do it for a newer release.

I guess you already know about IOCCC. But if you don’t, here is an exam­ple appli­ca­tion I wrote. That surely isn’t one of the most well writ­ten exam­ples, but since it is my first obfus­cated c pro­gram, I think it is also enough :)
I didn’t obfus­cated it using #define’s since by using -E gcc’s option you can easily retrieve the start­ing code. This is really a obfus­cated, chaotic pro­gram. And, of course, I won’t give you the solu­tion (but if you under­stand what it does, please let me know)!
There’s an issue: this code doesn’t fit into the blogspot layout. I really have to make a per­son­al­ized layout that allow me to include code snippets.

#include <stdio.h>
#include <string.h>
int bl(const char *) ;; int main (int na , char **a) { if (na != 2) return -1;;
printf("%cn", bl (*(a + 1)) + '0'); return 0; } int bl(const char *expr) { int
len = strlen(expr) * 2, i = 0, b = 0; enum S { $S, BO, BC, $E }; enum S s = $S;
char x; while (s != $E && i < (len / 2)){ x = *(expr + i); if (x == ' ') { i++;
continue; } switch (s) { case $S: if (x == 'x28') { s = BO; b++;} else s = $E;
break; case BO: case BC: if (x == 'x28') { s = BO; b++;} else if (x == 'x29')
{ --b; if (b == 0) { s = $S;; } else s = BC; } else { s = $E; } break; case $E:
default:return 1;break; } i++; } if ((b != 0) || (s == $E)) return 1;return 0;}