Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1002119
  • 博文数量: 150
  • 博客积分: 3017
  • 博客等级: 少校
  • 技术积分: 3829
  • 用 户 组: 普通用户
  • 注册时间: 2011-11-19 14:40
个人简介

Now in Baidu WISE team

文章分类

全部博文(150)

文章存档

2014年(8)

2013年(31)

2012年(111)

分类: C/C++

2012-10-28 01:11:30

许多程序会大量使用字符串。对于不同的字符串,我们希望能够有办法判断其相似程序。我们定义一套操作方法来把两个不相同的字符串变得相同,具体的操作方法为:

修改一个字符(如把“ a”替换为“ b”);
增加一个字符(如把“ abdd”变为“ aebdd”);
删除一个字符(如把“ travelling”变为“traveling”);
比如,对于“ abcdefg”和“abcdef”两个字符串来说,我们认为可以通过增加 /减少一个“g”的方式来达到目的。上面的两种方案,都仅需要一次。把这个操作所需要的次数定义为两个字符串的距离,而相似度等于“距离 +1”的倒数。也就是说, “abcdefg”和“abcdef”的距离为 1,相似度为 1/2=0.5。给定任意两个字符串,你是否能写出一个算法来计算它们的相似度呢?

 

这个题目其实就是最长相似子串LCS算法。具体参阅

http://blog.chinaunix.net/uid-26456800-id-3366849.html



 

点击(此处)折叠或打开

  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <string.h>
  4. #define MAX 1000
  5. #define min(a,b) ((a)<(b)?(a):(b))

  6. int test(char* a, char *b){
  7.     int asize = strlen(a);
  8.     int bsize = strlen(b);
  9.     int result[MAX][MAX] = {{0}};
  10.     int i = 0;
  11.     for(;i<asize;i++){
  12.         result[0][i] = (a[i] == b[0] ? 0:1);
  13.     }
  14.     for(i=0;i<bsize;i++){
  15.         result[i][0] = (a[0] == b[i] ? 0:1);
  16.     }
  17.     int row, col;
  18.     for(row = 1; row<bsize; row++){
  19.         for(col = 1; col<asize; col++){
  20.             int t1, t2, t3;
  21.             t1 = result[row-1][col-1] + (a[row] == b[col] ? 0 : 1);
  22.             t2 = result[row][col-1] + 1;
  23.             t3 = result[row-1][col] + 1;
  24.             result[row][col] = min(t3, min(t1,t2));
  25.         }
  26.     }
  27.     printf("%d \n", result[row-1][col-1]);
  28.         return(result[row-1][col-1]);
  29. }

  30. int main(){
  31.     char a[] = "abc";
  32.     char b[] = "abd";
  33.           test(a,b);
  34. }


 

阅读(1143) | 评论(0) | 转发(2) |
给主人留下些什么吧!~~