首页 > 代码库 > 编程之美——计算字符串相似度

编程之美——计算字符串相似度

2024-07-20 11:16:31   220人阅读

方法一：使用递归思想

代码：

 1 #include<iostream> 2 #include<string> 3 using namespace std; 4  5 int minValue(int t1,int t2,int t3); 6 int calculateStringDistance(string strA,int pAbegin,int pAend,string strB,int pBbegin,int pBend); 7  8 int main() 9 {10     string strA="hello";11     string strB="hi";12     cout<<calculateStringDistance(strA,0,strA.size(),strB,0,strB.size());13     return 0;14 }15 16 int calculateStringDistance(string strA,int pAbegin,int pAend,string strB,int pBbegin,int pBend)17 {18     if(pAbegin>pAend)19     {20         if(pBbegin>pBend)21             return 0;22         else23             return pBend-pBbegin+1;24     }25     if(pBbegin>pBend)26     {27         if(pAbegin>pAend)28             return 0;29         else30             return pAend-pAbegin+1;31     }32 33     if(strA[pAbegin]==strB[pBbegin])34         return calculateStringDistance(strA,pAbegin+1,pAend,strB,pBbegin+1,pBend);35     else36     {37         int t1=calculateStringDistance(strA,pAbegin+1,pAend,strB,pBbegin+1,pBend);38         int t2=calculateStringDistance(strA,pAbegin,pAend,strB,pBbegin+1,pBend);39         int t3=calculateStringDistance(strA,pAbegin+1,pAend,strB,pBbegin,pBend);40         return minValue(t1,t2,t3)+1;41     }42 }43 44 int minValue(int t1,int t2,int t3)45 {46     int t=min(t1,t2);47     return min(t,t3);48 }
View Code

上面的递归程序中，有些数据被重复计算了，可以使用一个二维数组存储递归过程中间值，避免不必要的递归过程

方法二：

 1 #include<iostream> 2 #include<string> 3 #include<cstring> 4 using namespace std; 5  6 int minValue(int t1,int t2,int t3); 7 int calculateStringDistance(string strA,int pAbegin,int pAend,string strB,int pBbegin,int pBend); 8  9 int momoDistance[100][100];10 11 int main()12 {13     string strA="abcdfef";14     string strB="f";15     memset(momoDistance,0,sizeof(momoDistance));16 17     cout<<calculateStringDistance(strA,0,strA.size()-1,strB,0,strB.size()-1);18 19     return 0;20 }21 22 int calculateStringDistance(string strA,int pAbegin,int pAend,string strB,int pBbegin,int pBend)23 {24     if(pAbegin>pAend)25     {26         if(pBbegin>pBend)27             return 0;28         else29             return pBend-pBbegin+1;30     }31     if(pBbegin>pBend)32     {33         if(pAbegin>pAend)34             return 0;35         else36             return pAend-pAbegin+1;37     }38 39     if(strA[pAbegin]==strB[pBbegin])40     {41         if(momoDistance[pAbegin+1][pBbegin+1]!=0)42             return momoDistance[pAbegin+1][pBbegin+1];43         else44         {45             momoDistance[pAbegin+1][pBbegin+1]=46             calculateStringDistance(strA,pAbegin+1,pAend,strB,pBbegin+1,pBend);47             return momoDistance[pAbegin+1][pBbegin+1];48         }49     }50     else51     {52         int t1,t2,t3;53         if(momoDistance[pAbegin+1][pBbegin+1]!=0)54             t1=momoDistance[pAbegin+1][pBbegin+1];55         else56         {57             t1=calculateStringDistance(strA,pAbegin+1,pAend,strB,pBbegin+1,pBend);58             momoDistance[pAbegin+1][pBbegin+1]=t1;59         }60 61         if(momoDistance[pAbegin+1][pBbegin]!=0)62             t2=momoDistance[pAbegin+1][pBbegin];63         else64         {65             t2=calculateStringDistance(strA,pAbegin+1,pAend,strB,pBbegin,pBend);66             momoDistance[pAbegin+1][pBbegin]=t2;67         }68 69         if(momoDistance[pAbegin][pBbegin+1]!=0)70             t3=momoDistance[pAbegin][pBbegin+1];71         else72         {73             t3=calculateStringDistance(strA,pAbegin,pAend,strB,pBbegin+1,pBend);74             momoDistance[pAbegin][pBbegin+1]=t3;75         }76 77         return minValue(t1,t2,t3)+1;78     }79 }80 81 int minValue(int t1,int t2,int t3)82 {83     int t=min(t1,t2);84     return min(t,t3);85 }
View Code

memset函数说明

以字节为单位对指向内存的4个字节赋值，每个都用ASCⅡ为1的字符去填充，转为二进制后，1就00000001，所以用memset对非字符型数组赋初值是不可取的！但是可以当作清零函数；

编程之美——计算字符串相似度


联系
我们