编程之美3.3的一道题，两字符串相似度定义为两字符串距离+1的倒数，而字符串距离又被定义为将一个字符串通过（1添加一个字符2删除一个字符3修改一个字符）这三种基本操作的步数。这样计算相似度其实就是计算距离，计算字符串距离实际上是经典的DP问题。
现在定义distance[i][j]含义为字符串a[0...i-1]和字符串b[0...j-1]的相似度，则可以知道：
1、distance[0][j] = j;distance[i][0] = i;
2、若a[i - 1] = b[j - 1]则distance[i][j] = distance[i - 1][j - 1];
3、若a[i - 1] != b[j - 1]则distance[i][j]= min(distance[i - 1][j - 1], distance[i - 1][j], distance[i][j - 1]) + 1;
第三种情况可以理解为，如果a字符串的第x个字符不等于b字符串的第y个字符，则可以：1）去掉a字符串的第x个字符，然后再将a[0...x-1]与b[0...y]比较；2）将a字符串的第x个字符修改为b的第y个字符，然后比较a[0...x-1]与b[0...y-1]；3）在a的字符串的第x个字符后面添加b的第y个字符，然后再将a[0...x]与b[0...y-1]比较；或者像以上三步一样操作b字符串；
这样得到如下程序：
1 #define min(a, b) ((a) > (b) ? (b) : (a))
2
3 int calculate_string_distance(char *str_a, char *str_b) {
4 int i, j;
5 int str_a_len = strlen(str_a);
6 int str_b_len = strlen(str_b);
7 //gcc允许这么做
8 //但ansi c是不允许这么做的
9 //最好还是用new或者全局数组
10 int distance[str_a_len + 1][str_b_len + 1];
11 for (i = 0; i <= str_a_len; ++i) {
12 distance[i][0] = i;
13 }
14 for (j = 0; j <= str_b_len; ++j) {
15 distance[0][j] = j;
16 }
17 for (i = 1; i <= str_a_len; ++i) {
18 for (j = 1; j <= str_b_len; ++j) {
19 distance[i][j] = distance[i - 1][j - 1];
20 if (str_a[i - 1] != str_b[j - 1]) {
21 distance[i][j] = min(distance[i][j],
22 distance[i - 1][j]);
23 distance[i][j] = min(distance[i][j],
24 distance[i][j - 1]);
25 distance[i][j]++;
26 }
27 }
28 }
29 return distance[str_a_len][str_b_len];
30 }
上面算法是非递归程序，如果要写递归代码，则相对简单，此处略，不过递归代码由于需要重复计算很多中情况，所以会非常慢。
posted on 2012-09-03 20:52
myjfm 阅读(667)
评论(0) 编辑 收藏 引用 所属分类:
算法基础