编程之美里面的计算字符串相似度的问题

totopper

自己把代码输入进去了，发现结果不对呀，代码如下

1. #include <string>
   
2. #include <iostream>
   
3. using namespace std;
   
4. int minValue(int &v1,int &v2, int &v3)
   
5. {
   
6.         int temp;
   
7.         if ( v1 > v2 )
   
8.                 temp = v2;
   
9.         else
   
10.                 temp = v1;
    
11.         if (temp > v3)
    
12.                 return v3;
    
13.         else
    
14.                 return temp;
    
15. }
    
16. 
    
17. int calstrdist(string strA, int pABegin, int pAEnd, string strB, int pBBegin, int pBEnd)
    
18. {
    
19.         if (pABegin > pAEnd)
    
20.                 {
    
21.                         if (pBBegin > pBEnd )
    
22.                                 return 0;
    
23.                         else
    
24.                                 return pBEnd-pBBegin+1;
    
25.                 }
    
26.         if (pBBegin > pBEnd )
    
27.                 {
    
28.                         if ( pABegin > pAEnd)
    
29.                                 return 0;
    
30.                         else
    
31.                                 return pAEnd-pABegin+1;
    
32.                 }
    
33.         if ( strA[pABegin] == strB[pBBegin])
    
34.                 return calstrdist(strA,pABegin+1,pAEnd,strB,pBBegin+1,pBEnd);
    
35.         else
    
36.                 {
    
37.                         int t1 = calstrdist( strA, pABegin+1, pAEnd, strB, pBBegin+2, pBEnd);
    
38.                         int t2 = calstrdist( strA, pABegin+2, pAEnd, strB, pBBegin+1, pBEnd);
    
39.                         int t3 = calstrdist( strA, pABegin+2, pAEnd, strB, pBBegin+2, pBEnd);
    
40. 
    
41.                         return minValue(t1,t2,t3)+1;
    
42.                 }
    
43. }
    
44. int main()
    
45. {
    
46.         string strA("123456");
    
47.         string strB("abcd");
    
48.         int dist = calstrdist(strA,0,strA.length()-1,strB,0,strB.length()-1);
    
49.         cout<<dist<<endl;
    
50. }
    

复制代码

预期输出6，但是测试结果是3，不知道为什么呢..

104359176

相似度有什么用？

umyspl

比如:

leewon1988

1. /**
   
2. *两个字符串，通过删除/添加/修改变为相同的字符串的最少操作
   
3. *字符串距离就是：操作+1
   
4. *字符串的相似度为（1/操作+1）
   
5. * */
   
6. #include <iostream>
   
7. #include <chrono>
   
8. using namespace std;
   
9. using namespace std::chrono;
   
10. 
    
11. int get_distance(char* left,int l_begin,int l_end,
    
12.                 char* right,int r_begin,int r_end)
    
13. {
    
14.         if(l_begin>=l_end)
    
15.         {
    
16.                 if(r_begin>=r_end)
    
17.                         return 0;
    
18.                 else
    
19.                         return r_end-r_begin;
    
20.         }
    
21.         if(r_begin>=r_end)
    
22.         {
    
23.                 if(l_begin>=l_end)
    
24.                         return 0;
    
25.                 else
    
26.                         return l_end-l_begin;
    
27.         }
    
28.         if(left[l_begin]==right[r_begin])
    
29.                 return get_distance(left,l_begin+1,l_end,
    
30.                                 right,r_begin+1,r_end);
    
31.         else
    
32.         {
    
33.                 int op1=get_distance(left,l_begin+1,l_end,
    
34.                                 right,r_begin+1,r_end);
    
35.                 int op2=get_distance(left,l_begin,l_end,
    
36.                                 right,r_begin+1,r_end);
    
37.                 int op3=get_distance(left,l_begin+1,l_end,
    
38.                                 right,r_begin,r_end);
    
39.                 int sum=[&]()
    
40.                 {
    
41.                         int mid;
    
42.                         if(op1>=op2)
    
43.                                 mid=op2;
    
44.                         else
    
45.                                 mid=op1;
    
46.                         if(mid>op3)
    
47.                                 mid=op3;
    
48.                         return mid+1;
    
49.                 }();
    
50.                 return sum;
    
51.         }
    
52. }
    
53. 
    
54. int** new_matrix(int l,int r)
    
55. {
    
56.         int** ptr=new int*[l];
    
57.         for(int i=0;i<l;++i)
    
58.         {
    
59.                 ptr[i]=new int[r];
    
60.                 for(int j=0;j<r;++j)
    
61.                 {
    
62.                         ptr[i][j]=-1;
    
63.                 }
    
64.         }
    
65.         return ptr;
    
66. }
    
67. 
    
68. void delete_matrix(int** ptr,int l)
    
69. {
    
70.         for(int i=0;i<l;++i)
    
71.                 delete[] ptr[i];
    
72.         delete[] ptr;
    
73. }
    
74. 
    
75. int get_distance_state(char* left,int l_begin,int l_end,
    
76.                 char* right,int r_begin,int r_end,int** state)
    
77. {
    
78. 
    
79.         if(state[l_begin][r_begin]!=-1)
    
80.                 return state[l_begin][r_begin];
    
81. 
    
82.         if(l_begin>=l_end)
    
83.         {
    
84.                 if(r_begin>=r_end)
    
85.                 {
    
86.                         state[l_begin][r_begin]=0;
    
87.                         return 0;
    
88.                 }
    
89.                 else
    
90.                 {
    
91.                         int dis=r_end-r_begin;
    
92.                         state[l_begin][r_begin]=dis;
    
93.                         return dis;
    
94.                 }
    
95.         }
    
96.         if(r_begin>=r_end)
    
97.         {
    
98.                 if(l_begin>=l_end)
    
99.                 {
    
100.                         state[l_begin][r_begin]=0;
     
101.                         return 0;
     
102.                 }
     
103.                 else
     
104.                 {
     
105.                         int dis= l_end-l_begin;
     
106.                         state[l_begin][r_begin]=dis;
     
107.                         return dis;
     
108.                 }
     
109.         }
     
110.         if(left[l_begin]==right[r_begin])
     
111.         {
     
112.                 int dis=get_distance(left,l_begin+1,l_end,
     
113.                                 right,r_begin+1,r_end);
     
114.                 state[l_begin][r_begin]=dis;
     
115.                 return dis;
     
116.         }
     
117.         else
     
118.         {
     
119.                 int op1=get_distance(left,l_begin+1,l_end,
     
120.                                 right,r_begin+1,r_end);
     
121.                 int op2=get_distance(left,l_begin,l_end,
     
122.                                 right,r_begin+1,r_end);
     
123.                 int op3=get_distance(left,l_begin+1,l_end,
     
124.                                 right,r_begin,r_end);
     
125.                 int sum=[&]()
     
126.                 {
     
127.                         int mid;
     
128.                         if(op1>=op2)
     
129.                                 mid=op2;
     
130.                         else
     
131.                                 mid=op1;
     
132.                         if(mid>op3)
     
133.                                 mid=op3;
     
134.                         return mid+1;
     
135.                 }();
     
136.                 state[l_begin][r_begin]=sum;
     
137.                 return sum;
     
138.         }
     
139. }
     
140. 
     
141. int main(int argc,char* argv[])
     
142. {
     
143.         char left[]={"123456"};
     
144.         char right[]={"abcd"};
     
145.        
     
146.         int** state=new_matrix(sizeof(left)/sizeof(char),
     
147.                         sizeof(right)/sizeof(char));
     
148.         int dis=get_distance_state(left,0,sizeof(left)/sizeof(char),
     
149.                         right,0,sizeof(right)/sizeof(char),state);
     
150.         cout<<"with state: "<<dis<<endl;
     
151.         delete_matrix(state,sizeof(left)/sizeof(char));
     
152. }
     

复制代码

楼主代码有问题吧？！
以上是我的代码

1. g++ -g -Wall -std=c++11 str_sim.cpp
   
2. ./a.out
   

复制代码

1. with state: 6

复制代码

leewon1988

上面代码有些地方为了练习一下C++11，胡乱使用的
大家忽略不计！
结果是没问题的