【转】字符串相似度

昨天论坛看到的，简单写了一下 题目： 一个字符串可以通过增加一个字符，删除一个字符，替换一个字符得到另外一个字符串，假设，我们把从字符串A转换成字符串B，前面3种操作所执行的最少次数称为AB相似度 如  abc adc  度为 1       ababababa babababab 度为 2       abcd acdb 度为2
 字符串相似度算法可以使用 Levenshtein Distance算法(中文翻译：编辑距离算法) 这算法是由俄国科学家Levenshtein提出的。其步骤

StepDescription

1 Set n to be the length of s. Set m to be the length of t. If n = 0, return m and exit. If m = 0, return n and exit. Construct a matrix containing 0..m rows and 0..n columns.
2 Initialize the first row to 0..n. Initialize the first column to 0..m.
3 Examine each character of s (i from 1 to n).
4 Examine each character of t (j from 1 to m).
5 If s[i] equals t[j], the cost is 0. If s[i] doesn't equal t[j], the cost is 1.
6 Set cell d[i,j] of the matrix equal to the minimum of: a. The cell immediately above plus 1: d[i-1,j] + 1. b. The cell immediately to the left plus 1: d[i,j-1] + 1. c. The cell diagonally above and to the left plus the cost: d[i-1,j-1] + cost.
7 After the iteration steps (3, 4, 5, 6) are complete, the distance is found in cell d[n,m].
Cpp代码 复制代码 收藏代码
  1. #include <iostream>  
  2. #include <vector>  
  3. #include <string>  
  4. using namespace std;  
  5.   
  6. //算法  
  7. int ldistance(const string source,const string target)  
  8. {  
  9.     //step 1  
  10.   
  11.     int n=source.length();  
  12.     int m=target.length();  
  13.     if (m==0) return n;  
  14.     if (n==0) return m;  
  15.     //Construct a matrix  
  16.     typedef vector< vector<int> >  Tmatrix;  
  17.     Tmatrix matrix(n+1);  
  18.     for(int i=0; i<=n; i++)  matrix[i].resize(m+1);  
  19.   
  20.     //step 2 Initialize  
  21.   
  22.     for(int i=1;i<=n;i++) matrix[i][0]=i;  
  23.     for(int i=1;i<=m;i++) matrix[0][i]=i;  
  24.   
  25.      //step 3  
  26.      for(int i=1;i<=n;i++)  
  27.      {  
  28.         const char si=source[i-1];  
  29.         //step 4  
  30.         for(int j=1;j<=m;j++)  
  31.         {  
  32.   
  33.             const char dj=target[j-1];  
  34.             //step 5  
  35.             int cost;  
  36.             if(si==dj){  
  37.                 cost=0;  
  38.             }  
  39.             else{  
  40.                 cost=1;  
  41.             }  
  42.             //step 6  
  43.             const int above=matrix[i-1][j]+1;  
  44.             const int left=matrix[i][j-1]+1;  
  45.             const int diag=matrix[i-1][j-1]+cost;  
  46.             matrix[i][j]=min(above,min(left,diag));  
  47.   
  48.         }  
  49.      }//step7  
  50.       return matrix[n][m];  
  51. }  
  52. int main(){  
  53.     string s;  
  54.     string d;  
  55.     cout<<"source=";  
  56.     cin>>s;  
  57.     cout<<"diag=";  
  58.     cin>>d;  
  59.     int dist=ldistance(s,d);  
  60.     cout<<"dist="<<dist<<endl;  
  61. }  
  62. #include <iostream>  
  63. #include <vector>  
  64. #include <string>  
  65. using namespace std;  
  66.   
  67. //算法  
  68. int ldistance(const string source,const string target)  
  69. {  
  70.     //step 1  
  71.   
  72.     int n=source.length();  
  73.     int m=target.length();  
  74.     if (m==0) return n;  
  75.     if (n==0) return m;  
  76.     //Construct a matrix  
  77.     typedef vector< vector<int> >  Tmatrix;  
  78.     Tmatrix matrix(n+1);  
  79.     for(int i=0; i<=n; i++)  matrix[i].resize(m+1);  
  80.   
  81.     //step 2 Initialize  
  82.   
  83.     for(int i=1;i<=n;i++) matrix[i][0]=i;  
  84.     for(int i=1;i<=m;i++) matrix[0][i]=i;  
  85.   
  86.      //step 3  
  87.      for(int i=1;i<=n;i++)  
  88.      {  
  89.         const char si=source[i-1];  
  90.         //step 4  
  91.         for(int j=1;j<=m;j++)  
  92.         {  
  93.   
  94.             const char dj=target[j-1];  
  95.             //step 5  
  96.             int cost;  
  97.             if(si==dj){  
  98.                 cost=0;  
  99.             }  
  100.             else{  
  101.                 cost=1;  
  102.             }  
  103.             //step 6  
  104.             const int above=matrix[i-1][j]+1;  
  105.             const int left=matrix[i][j-1]+1;  
  106.             const int diag=matrix[i-1][j-1]+cost;  
  107.             matrix[i][j]=min(above,min(left,diag));  
  108.   
  109.         }  
  110.      }//step7  
  111.       return matrix[n][m];  
  112. }  
  113. int main(){  
  114.     string s;  
  115.     string d;  
  116.     cout<<"source=";  
  117.     cin>>s;  
  118.     cout<<"diag=";  
  119.     cin>>d;  
  120.     int dist=ldistance(s,d);  
  121.     cout<<"dist="<<dist<<endl;  
  122. }  
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/qqxiongmao/p/3039139.html