Lowden

now

字符串匹配编辑距离(C语言实现,非DPA算法)

 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 **= (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 

posted on 2010-11-18 16:46 Lowden 阅读(184) 评论(0)  编辑  收藏


只有注册用户登录后才能发表评论。
网站导航:

My Links

Blog Stats

常用链接

留言簿

随笔分类

随笔档案

文章分类

文章档案

好友链接

搜索

最新评论

阅读排行榜

评论排行榜