c语言计算莱文斯坦距离

1.源码实现

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

int min(int x, int y)
{
    return x < y ? x : y;
}

int getdistance(char *a, char *b, int m, int n, int **c)
{
    int d;
    int i, j;

    for(i=0; i<=m; i++)
    {
        c[i][0] = i;
    }

    for(i=0; i<=n; i++)
    {
        c[0][i] = i;
    }

    for(i=1; i<=m; i++)
    {
        for(j=1; j<=n; j++)
        {
            d = min(c[i-1][j], c[i][j-1]) + 1;

            /*printf("c[%d][%d] = %d\n", i-1, j, c[i-1][j]);
            printf("c[%d][%d] = %d\n", i, j-1, c[i][j-1]);
            printf("c[%d][%d] = %d\n", i-1, j-1, c[i-1][j-1]);*/

            if(a[i-1] == b[j-1])
            {
                d = min(d, c[i-1][j-1]);
            }
            else
            {
                d = min(d, c[i-1][j-1]+1);
            }

            c[i][j] = d;
        }
    }

    /*printf("c[%d][%d] = %d\n", m, n, c[m][n]);*/

    return c[m][n];
}

int main()
{
    char a[1024];
    char b[1024];
    int *c[1024];
    int d;
    int m;
    int n;
    int i, j;

    while(scanf("%s", a) != EOF)
    {
        scanf("%s", b);

        m = strlen(a);
        n = strlen(b);

        if(m >= n)
        {
            /*printf("%s %s\n", a, b);*/

            for(i=0; i<=m; i++)
            {
                c[i] = NULL;
                c[i] = (int *)malloc((n+1)*sizeof(int));
            }

            d = getdistance(a, b, m, n, c);

            for(i=0; i<m; i++)
            {
                free(c[i]);
                c[i] = NULL;
            }
        }
        else
        {
            for(i=0; i<=n; i++)
            {
                c[i] = NULL;
                c[i] = (int *)malloc((m+1)*sizeof(int));
            }

            d =  getdistance(b, a, n, m, c);

            for(i=0; i<m; i++)
            {
                free(c[i]);
                c[i] = NULL;
            }
        }

        printf("%d\n", d);
    }

    return 0;
}

2.编译源码

$ gcc -o example examle.c -std=c89

3.运行及其结果

$ ./example
abcdefg
abcdef
1
abcde
abcdf
1
abcde
bcdef
2