计算两个字符串的编辑距离的快速算法

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define min(val1, val2) (((val1) < (val2)) ? (val1) : (val2)) 

#define min3operators(val1, val2, val3) (min(val1, val2) < min(val1, val3)) ? min(val1, val2) : min(val1, val3) 

int levenshtein(const char *string1, const char *string2)

{

int n = 0;

int m = 0;

int i = 0;

int j = 0;

int cost = 0;

int *v0 = NULL;

int *v1 = NULL;

if(NULL == string1 || NULL == string2)

{

return -1;

}

n = strlen(string1);

m = strlen(string2);

if(0 == n)

{

return m;

}

if(0 == m)

{

return n;

}

v0 = (int *)malloc(sizeof(int) * (m + 1));

v1 = (int *)malloc(sizeof(int) * (m + 1));

for(i=0; i<= m; i++)

{

v0[i] = i;

}

for(i=1; i<= n; i++)

{

for(j=1; j<= m; j++)

{

if(1 == j)

{

v1[0] = i;

}

if(string1[i-1] == string2[j-1])

{

cost = 0;

}

else

{

cost = 1;

}

v1[j]=min3operators((v1[j-1]+1), (v0[j]+1), (v0[j-1])+cost);

}

for(j=0; j<= m; j++)

{

v0[j] = v1[j];

}

}

return v1[m];

}

int main()

{

printf("levenshtein:%d\n", levenshtein("GUMBOLUabcdefgg", "GAMBOLabcedefdgh"));

printf("min3operators:%d\n", min3operators(9, 8, 7));

return 0;

}