字符串相似度

   一个字符串可以通过增加一个字符，删除一个字符，替换一个字符得到另外一个字符串，假设，我们把从字符串A转换成字符串B，前面3种操作所执行的最少次数称为AB相似度
如 abc adc  度为 1
   ababababa babababab 度为 2
   abcd acdb 度为2

 

   先是看到编程之美上有这道题,但是感觉理解起来不是很爽,特别那句如何修改递归程序呢？留给读者自己完成吧!!现在越来越以批判的眼光看待这本书了,判断两个链表公共节点那题,说实话这本书上的很rubbish.看我blog里面的那篇吧^_^

  

    字符串相似度算法可以使用 Levenshtein Distance算法(中文翻译：编辑距离算法) 这算法是由俄国科学家Levenshtein提出的。其步骤

Step	Description
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].

 

 

 

#include <stdio.h>
#include <stdlib.h>

#define min2(a,b) (a)<(b) ? (a) : (b)
#define min3(a,b,c) min2((min2(a,b)),(c))

int like_degree(char* str1, char* str2)
{
   int i;
   int j;
   int cost;
   int len1 = strlen(str1);
   int len2 = strlen(str2);
   int d[len1+1][len2+1];
   int min_degree;
   
   memset(d,0,sizeof(d));
   
   for(i=0;i<len1+1;i++)
      d[0][i] = i;
   for(j=1;i<len2+1;j++)
      d[j][0] = j;
      
   for(i=1;i<=len1;i++)
    for(j=1;j<=len2;j++)
     {
       if(str1[i-1] == str2[j-1])
          cost = 0;
       else
          cost = 1;
        
        d[i][j] = min3(d[i-1][j]+1,d[i][j-1]+1,d[i-1][j-1]+cost);
        printf("d[%d]d[%d] is %d\n",i,j,d[i][j]);
     }

   min_degree = d[i-1][j-1];
   
   printf("str1:%s\t\tand\t\tstr2:%s\nlike degree is %d\n",str1,str2,min_degree);
   return min_degree;
}
 
int main(int argc, char *argv[])
{
  char* str1 = "abcd";
  char* str2 = "acdb";
  
  like_degree( str1, str2);
  
  system("PAUSE");    
  return 0;
}


先开始的时候那两个Min macro没有加括号,居然答案错了,还以为算法错了呢^_^.宏真是个让人又爱又恨得东西...我先想着我这里没传min(a+b,c)这样的应该没问题的....