计算字符串相似度

问题：给定一个源串和目标串，能够对串进行如下操作：（2012百度、google）

1.在给定位置上插入一个字符

2.替换任意字符

3.删除任意字符

写一个程序，返回最小操作数，使得进行这些操作后源串等于目标串，源串和目标串的长度都小于2000

类似的表述形式如下：

许多程序会大量使用字符串。对于不同的字符串，我们希望能够有办法判断其相似程序。我们定义一套操作方法来把两个不相同的字符串变得相同，具体的操作方法为：

　　1.修改一个字符（如把“a”替换为“b”）;

　　2.增加一个字符（如把“abdd”变为“aebdd”）;

　　3.删除一个字符（如把“travelling”变为“traveling”）;

　　比如，对于“abcdefg”和“abcdef”两个字符串来说，我们认为可以通过增加/减少一个“g”的方式来达到目的。上面的两种方案，都仅需要一次。把这个操作所需要的次数定义为两个字符串的距离，而相似度等于“距离+1”的倒数。也就是说，“abcdefg”和“abcdef”的距离为1，相似度为1/2=0.5。

　　给定任意两个字符串，你是否能写出一个算法来计算它们的相似度呢？

解答：

首先考虑如何把这个问题转化成规模较小的同样的子问题。如果有两个串A=xabcdae和B=xfdfa，它们的第一个字符是相同的，只要计算A[2,...,7]=abcdae和B[2,...,5]=fdfa的距离就可以了。但是如果两个串的第一个字符不相同，那么可以进行如下的操作（lenA和lenB分别是A串和B串的长度）。

1.删除A串的第一个字符，然后计算A[2,...,lenA]和B[1,...,lenB]的距离。
2.删除B串的第一个字符，然后计算A[1,...,lenA]和B[2,...,lenB]的距离。
3.修改A串的第一个字符为B串的第一个字符，然后计算A[2,...,lenA]和B[2,...,lenB]的距离。
4.修改B串的第一个字符为A串的第一个字符，然后计算A[2,...,lenA]和B[2,...,lenB]的距离。
5.增加B串的第一个字符到A串的第一个字符之前，然后计算A[1,...,lenA]和B[2,...,lenB]的距离。
6.增加A串的第一个字符到B串的第一个字符之前，然后计算A[2,...,lenA]和B[1,...,lenB]的距离。

在这个题目中，我们并不在乎两个字符串变得相等之后的字符串是怎样的。所以，可以将上面的6个操作合并为：

1.一步操作之后，再将A[2,...,lenA]和B[1,...,lenB]变成相字符串。
2.一步操作之后，再将A[2,...,lenA]和B[2,...,lenB]变成相字符串。
3.一步操作之后，再将A[1,...,lenA]和B[2,...,lenB]变成相字符串。

　　这样，很快就可以完成一个递归程序。

 1 #include<iostream>
 2 #include<cmath>
 3 using namespace std;
 4 int a[100][100];
 5 int caculateStringDistance(const char* strA,int Abegin,int Aend,const char *strB,int Bbegin,int Bend)
 6 {
 7     if(a[Abegin][Bbegin]>=0)  //该子问题以计算过
 8         return a[Abegin][Bbegin];  
 9     if(Abegin>Aend)    //边界条件
10     {
11         if(Bbegin>Bend) 
12             return 0;
13         else
14         {
15             a[Abegin][Bbegin]=Bend-Bbegin+1;
16             return a[Abegin][Bbegin];
17         }
18     }
19     if(Bbegin>Bend)  //边界条件
20     {
21         if(Abegin>Aend) 
22             return 0;
23         else
24         {
25             a[Abegin][Bbegin]=Aend-Abegin+1;
26             return a[Abegin][Bbegin];
27         }
28     }
29     if(strA[Abegin]==strB[Bbegin]) 
30         a[Abegin][Bbegin]=caculateStringDistance(strA,Abegin+1,Aend,strB,Bbegin+1,Bend);
31     else
32     {
33         int x=caculateStringDistance(strA,Abegin+1,Aend,strB,Bbegin,Bend);
34         int y=caculateStringDistance(strA,Abegin,Aend,strB,Bbegin+1,Bend);
35         int z=caculateStringDistance(strA,Abegin+1,Aend,strB,Bbegin+1,Bend);
36         a[Abegin][Bbegin]=min(x,min(y,z))+1;
37     }
38     return a[Abegin][Bbegin];
39 }
40 int getDistance(const char* strA,const char* strB)
41 {
42     int m=strlen(strA);
43     int n=strlen(strB);
44     memset(a,-1,sizeof(a));   //将a的值都设置为-1
45     return caculateStringDistance(strA,0,m-1,strB,0,n-1);
46 }
47  int main()
48  {
49      char *str1=new char[100],*str2=new char[100];
50     cout<<"input first string:";
51     cin>>str1;
52     cout<<"input second string:";
53     cin>>str2;
54     cout<<"the distance is:";
55     cout<<getDistance(str1,str2)<<endl;
56     delete []str1;
57     delete []str2;
58  }

View Code

结果：