1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4
5 int _Min(int a,int b,int c)
6 {
7 int min=a;
8 if (b <min)
9 min=b;
10 if(c <min)
11 min=c;
12 return min;
13 }
14
15 int ComputeDistance(char s[],char t[])
16 {
17 int n = strlen(s);
18
19 int m = strlen(t);
20
21 //int d[][] = new int[n + 1, m + 1]; // matrix
22 int **d = (int **)malloc((n+1) * sizeof(int *));
23 for(int i=0; i<=n; ++i)
24 {
25 d[i] = (int *)malloc((m+1) * sizeof(int));
26 }
27 // Step 1
28 if (n == 0)
29 {
30 return m;
31 }
32
33 if (m == 0)
34 {
35 return n;
36 }
37
38 // Step 2
39 for (int i = 0; i <= n; i++)
40 {
41 d[i][0] =i;
42 }
43
44 for (int j = 0; j <= m; d[0][j] = j++)
45 {
46 d[0][j] =j;
47 }
48
49 // Step 3
50 for (int i = 1; i <= n; i++)
51 {
52 //Step 4
53 for (int j = 1; j <= m; j++)
54 {
55 // Step 5
56 int cost = (t[j-1] == s[i-1]) ? 0 : 1;
57
58 // Step 6
59 d[i][j] = _Min(d[i-1][j]+1, d[i][j-1]+1,d[i-1][j-1]+cost);
60 }
61 }
62 // Step 7
63 return d[n][m];
64 }
65
66 int main(int argc, char *argv[])
67 {
68 char a[9999];
69 char b[9999];
70 printf("请输入字符串1\n");
71 scanf("%s",&a);
72 printf("请输入字符串2\n");
73 scanf("%s",&b);
74 int result= ComputeDistance(a,b);
75 printf("%d\n",result);
76 system("PAUSE");
77 return 0;
78 }
79