编辑距离问题

[效云 李]

问题描述 ：
设A和B是2个字符串。要用最少的字符操作将字符串A 转换为字符串B,这里所说的字符操作包括:
(1)删除一个字符 ；
(2)插入一个字符 ；
(3)将一个字符改为另一个字符 。
将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为d(A,B)。试设计一个有效算法，对任给的2个字符串A和B,计算出
它们的编辑距离d(A,B)。
编程任务 ：
对于给定的字符串A和字符串B ，编程计算其编辑距离d(A,B)。
数据输入 ：
输入是由多组输入数据组成，每组数据由两行组成，第一行是字符串A ，第二行是字符串B(A、B字符串长度都小于2000) 。当A=0，B=0表示程
序结束。
结果输出:
输出的每1行的值是编辑距离d(A,B)，每组输出值之间换行担不需要空行。
输入示例：
fxpimu
xwrs
0
0
输出示例:
5

这就是王晓东那书后的一个习题，以后大家可以一起看那书，然后讨论，如果把那书的题给全杀了，估计就很猛了

[higer]

这个程序可以利用"求最长公共子序列"的算法。下面是我的C算法，由于没有测试用例，可能在某些边界会出问题。另外，程序貌似写的不精炼，请多指教。
#include "stdio.h"
#include <string.h>
int cc[2000][2000];
int bb[2000][2000];
void edit_length(int m,int n,char* a,char* b)
{
int i,j;
for(i=1;i<=m;i++) cc[i][0]=0;
for(j=1;j<=n;j++) cc[0][j]=0;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
{
if(a[i]==b[j])
{cc[i][j]=cc[i-1][j-1]+1;bb[i][j]=1;}
else if(cc[i-1][j]>=cc[i][j-1])
{cc[i][j]=cc[i-1][j];bb[i][j]=2;}
else
{cc[i][j]=cc[i][j-1];bb[i][j]=3;}
}
}
int main()
{
char a[2000],b[2000];
int i=1,j=1;
int c;

while((c=getchar())!='\n')
{
a[i]=c;
i++;
}
a[i]='\0';
while((c=getchar())!='\n')
{
b[j]=c;
j++;
}
b[j]='\0';

int m=i-1,n=j-1;
printf("%d,%d\n",m,n);
edit_length(m,n,a,b);//计算最长公共子序列的长度

int num=0;//存放计算的结果

if(m<=n){
num=n-cc[m][n];
}
else{
int k1=0,k2=0;
int flag=1;//标志，跳出双重循环
for (k1=1;flag&&k1<=m;k1++)
for (k2=1;flag&&k2<=n;k2++){
if(bb[k1][k2]==1)
flag=0;//跳出
}
if ((m-k1)>=(n-k2)) {
num=m-cc[m][n];
}
else{
int temp=k1-cc[m][n]+n-k2;
num=temp>m?m:temp;
}
}
printf("%d\n",num);
return 0;

[李效云]

   int i,j;
       for(i=1;i<=m;i++) cc[i][0]=0;
       for(j=1;j<=n;j++) cc[0][j]=0;
       for(i=1;i<=m;i++)
               for(j=1;j<=n;j++)
               {
                       if(a[i]==b[j])
                       {cc[i][j]=cc[i-1][j-1]+1;bb[i]

[j]=1;}
                       else if(cc[i-1][j]>=cc[i][j-1])
                       {cc[i][j]=cc[i-1][j];bb[i][j]=2;}
                       else
                       {cc[i][j]=cc[i][j-1];bb[i][j]=3;}
               }

由于你在初始话的时候，是从1开始的，所以你在动态规划的时候                        {cc[i][j]=cc[i-1][j-1]+1;bb[i]

[j]=1;}
                       else if(cc[i-1][j]>=cc[i][j-1])
                       {cc[i][j]=cc[i-1][j];bb[i][j]=2;}
                       else
                       {cc[i][j]=cc[i][j-1];bb[i][j]=3;}

这句肯定出问题，结果要对才怪呢。
还有，你就不能用动态的数组吗？
那样测试用例超过2000，你怎么办啊？
我就看到这两点不知道对不

[higer]

由于cc和bb都定义成为全局变量，编译器会将它们存放在"静态存储区"，所以它们的默认初始值都是为0的，所以你说的第一个问题并不存在。当然，定义
变量而没有初始化的确是个不好的习惯。
还有，你说使用动态数组，那么对于C而言（我这里用的是C），动态数组要使用malloc函数，个人觉得比较麻烦，对于一些算法设计题，如果题目明确告
诉了"规模"，而且内存允许，那么这么定义是没什么问题的，虽然浪费了一些不必要的空间。

[李效云]

恩，怎么说呢，练习练习用动态数组没啥害处的，这样面试的时候，你写出来用动态的总比不用动态的好吧，
要习惯了，即使用了malloc，也就是1-2分钟的事情，没啥。
闲麻烦用STL里的VECTOR啊，这个挺好是，而且STL都很高效的，还是熟悉STL，虽然用VECTOR也没啥：（

2009/4/10 higer <higerin...@gmail.com>

[higer]

以前看过STL，早忘了，现在我想先拿C好好练练基本的算法，之后把STL温习一遍，尝尝"C++的美餐"。呵呵。

On Apr 10, 11:28 pm, 李效云 <lixiaoyun...@gmail.com> wrote:
> 恩，怎么说呢，练习练习用动态数组没啥害处的，这样面试的时候，你写出来用动态的总比不用动态的好吧，
> 要习惯了，即使用了malloc，也就是1-2分钟的事情，没啥。
> 闲麻烦用STL里的VECTOR啊，这个挺好是，而且STL都很高效的，还是熟悉STL，虽然用VECTOR也没啥：（
>

> 2009/4/10 higer <higerinbeij...@gmail.com>