经典ACM算法合集经典ACM算法合集(6)

b. 函数d()计算两字符串的编辑距离：
①用edit标记所比较的字符是否相同，相同为0，不同为1；
②分别用m、n存储字符串a、b的长度，用数组d[i][j] 存储长度分别为i、j的两字符串的编辑距离，问题的最优值记录于d[n][m]中；
③利用递归式写出计算d[i][j]的递归算法。

4、源程序：

#include <iostream>
using namespace std;

int min(int a, int b, int c)
{
int temp = (a < b ? a : b);
return (temp < c? temp : c);
}

int d(char* a, char* b)
{
int m = strlen(a);
int n = strlen(b);
int i,j ,temp;
int **d;
d=(int **)malloc(sizeof(int *)*(m+1));

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

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新人文社科经典ACM算法合集经典ACM算法合集(6)全文阅读和word下载服务。