《编程之美》读书笔记11： 3.3 计算字符串的相似度
很经典的可使用动态规划方法解决的题目，和计算两字符串的最长公共子序列相似。
设Ai为字符串A(a1a2a3 … am)的前i个字符（即为a1,a2,a3 … ai）
设Bj为字符串B(b1b2b3 … bn)的前j个字符（即为b1,b2,b3 … bj）
设 L(i , j)为使两个字符串和Ai和Bj相等的最小操作次数。
当ai等于bj时 显然L(i, j)=L(i-1, j-1)
当ai不等于bj时
若将它们修改为相等，则对两个字符串至少还要操作L(i-1, j-1)次
若删除ai或在Bj后添加ai，则对两个字符串至少还要操作L(i-1, j)次
若删除bj或在Ai后添加bj，则对两个字符串至少还要操作L(i, j-1)次
此时L(i, j)=min( L(i-1, j-1), L(i-1, j), L(i, j-1) ) + 1
显然，L(i, 0)=i，L(0, j)=j, 再利用上述的递推公式，可以直接计算出L(i, j)值。
为了保持与书中代码一致，下面的函数参数类型是string,而不是char*。
distance_1
1
int string_distance(const string& sa, const string& sb)
2
{
3
const int sz_a=sa.size()+1;
4 const int sz_b=sb.size()+1;
5 int i,j,k,tmp;
6 vector< vector<int> > arr(sz_a, vector<int>(sz_b) );
7 for (i=0; i<sz_a; ++i) arr[i][0]=i;
8 for (j=0; j<sz_b; ++j) arr[0][j]=j;
9
10
for (i=1; i<sz_a; ++i){
11 for (j=1; j<sz_b; ++j){
12 if( sa[i-1] == sb[j-1]) arr[i][j]=arr[i-1][j-1];
13 else{
14 tmp= arr[i-1][j] > arr[i][j-1] ? arr[i][j-1] : arr[i-1][j];
15 if (tmp>arr[i-1][j-1]) tmp=arr[i-1][j-1];
16 arr[i][j]=tmp+1;
17
}
18 }
19 }
20 return arr[sz_a-1][sz_b-1];
21
}
22
23
distance_2
1int string_distance2(const string& sa, const string& sb)
2{
3 const int sz_a=sa.size()+1;
4 const int sz_b=sb.size()+1;
5 int sz_max=sz_a;
6 int sz_min=sz_b;
7 const char *longer=sa.data();
8 const char *shorter=sb.data();
9 if (sz_a < sz_b){
10 sz_max=sz_b;
11 sz_min=sz_a;
12 longer=sb.data();
13 shorter=sa.data();
14 }
15 int i,j,k,tmp;
16 vector<int> arr(sz_min+1);
17 for (j=0; j<sz_min; ++j) arr[j+1]=j;
18
19 for (i=1; i<sz_max; ++i){
20 arr[0]=i;
21 for (j=1; j<sz_min; ++j){
22 if( longer[i-1] != shorter[j-1]) {
23 tmp= arr[j+1] > arr[j] ? arr[j] : arr[j+1];
24 if (tmp>arr[j-1]) tmp=arr[j-1];
25 arr[j]=tmp+1; //tmp= min(arr[j-1],arr[j],arr[j+1])
26 }
27 }
28 for(j=sz_min-1; j>=0; --j) arr[j+1]=arr[j];
29 }
30 return arr[sz_min];
31}
32
33
上面的代码还可进一步优化，比如通过指针而不是数组名来访问内存。如果内存足够大，可以多申请空间，每次循环，通过修改保存的数据起始位置，避免内存复制。
补充：字符串的相似度，就是求编辑距离（edit distance）。