编程之美3.3:字符串相似度

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

修改一个字符（如把“ 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

 

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

int test(char* a, char *b){
    int asize = strlen(a);
    int bsize = strlen(b);
    int result[MAX][MAX] = {{0}};
    int i = 0;
    for(;i<asize;i++){
        result[0][i] = (a[i] == b[0] ? 0:1);
    }
    for(i=0;i<bsize;i++){
        result[i][0] = (a[0] == b[i] ? 0:1);
    }
    int row, col;
    for(row = 1; row<bsize; row++){
        for(col = 1; col<asize; col++){
            int t1, t2, t3;
            t1 = result[row-1][col-1] + (a[row] == b[col] ? 0 : 1);
            t2 = result[row][col-1] + 1;
            t3 = result[row-1][col] + 1;
            result[row][col] = min(t3, min(t1,t2));
        }
    }
    printf("%d \n", result[row-1][col-1]);
        return(result[row-1][col-1]);
}

int main(){
    char a[] = "abc";
    char b[] = "abd";
          test(a,b);
}